# Questions tagged [strings]

Questions about sequences of symbols, sets thereof and their properties as well as uses.

508 questions
Filter by
Sorted by
Tagged with
1 vote
28 views

### Sparse bit string pattern matching

Suppose there are two strings of bits. Let's call them the needle (n) and the haystack (h). We'll say that the needle matches ...
1k views

### Compression of domain names

I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
4k views

### Convert given string to palindrome with given substring

Given strings s1 and s2, consider the problem of converting s1 to a palindrome string ...
1 vote
73 views

### Finding the subset of a dictionary that has the minimum edit distance to a given string

I'm looking for the most efficient way of solving an Levenshtein edit distance problem. We are given as input: A set of strings S of size ...
80 views

### Is solving Binary String Matching equivalent to Solving All type of string matching?

This might be an irritating, naive question, but please bear with me. If an algorithm/code solves the string matching problem for a binary string, does not it imply that the algo/code actually solves ...
1 vote
176 views

### Sequence alignment with one to many characters

I'm trying to align a sequence of characters together, I found that sequence alignment algorithms which use dynamic programming like Needleman-Wunsch or Smith–Waterman only align one character with ...
1 vote
466 views

### finding all cyclic substrings of a string

I have been stuck on this problem for a while now; any help would be appreciated. Given a string S, find the number of distinct substrings which are composed of 2 or more consecutive strings. For ...
83 views

### Find a substring length $k$ with maximum occurrences

Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string. We want $O(S)$ time complexity in an average case. I think the solution lies in sophisticated ...
1k views

### calculating the string similarity of an optimal alignment

description of the algorithms behavior I have two strings s1 and s2, with $len\_s1 <= len\_s2$. I would like to find the ...
107 views

81 views

### Shortest string which all input strings is its substring

Given a set of input strings, how do I find a shortest string S so that all input strings appear as a substring of S? for example: ...
18 views

### Optimizing the number of XML-like tags where only the innermost tag is respected

Given a string of characters (say a, b, ...) I want to wrap those characters by tags ...
70 views

### Number of bit string interpretations correct?

Suppose you are given a bit string $B[1 ... n]$. Now, suppose that some bits are just padding bits conveying no information, the rest of the bits may be permuted and some meaningful (that is, non-...
1 vote
122 views

### Find the no of substrings a character is part of

I am looking for a O(1) solution for finding the number of substrings a character is part of. For instance, let s = "abcde" and all substrings of s are <...
235 views

### String Search - how to find the "most" accurate string?

Assume I have the following list of companies: Apple Big Apple Google Then I have this sample string: Big Apple is a company that is trying to be the next Google. Given the list of companies and ...
1 vote
79 views

### Reconstructing a string from two its partitions into substrings of varying size

Given two unordered partitions of the same string over a finite alphabet into substrings, how hard is it to reconstruct the original string? If multiple solutions exist, any one will suffice. Under an ...
246 views

### Is there an elegant algorithm for applying multiple simultaneous search-and-replace operations to a string?

The operation I'm interested in is a slight twist on your standard search-and-replace operation, in that instead of a single pair of arguments (replaceme and ...
79 views

### ASCII invariant string for base64 Encoding

I know the basics about base64 encoding, but thinking about it abstractly I have a theoretical question. If we consider base64 a mathematical function(in our case computable), Does there exists an ...
217 views

### Longest prefix of string S that is also a sub-prefix of S in linear time

As the question suggest. I want an algorithm that runs in linear time which finds the longest prefix of a substring that is a sub-prefix of the same string. Formally: Given a string $S$ of length $n$,...
1 vote
215 views

### Is there a faster alternative to Aho-Corasick when searching for any occurrence rather than all occurrences of each of the substrings?

Aho-Corasick can result in a quadratic number of matches because it finds all occurrences of each searched-for substring. What is a faster algorithm or modification to this one to simply determine if ...
204 views

### A Markov algorithm that does unary multiplication

I am learning Markov algorithms and came across the paper Markov Algorithm by CHEN Yuanmi. I am trying to understand the following example (well, any of the examples in the paper). Example 3: ...
53 views

### Correct way to encode strings

I'm interested in analyzing the randomness of strings using relative count for 1-, 2-, etc tuples. E.g. for a long string "abbccba.." with an alphabet <...
724 views

### Can we prove that any set of finite strings without substrings is finite?

I want to prove (or disprove) the following conjecture: Let $\Sigma$ be a finite alphabet, and let $L \subseteq \Sigma^*$ satisfy that there are no $v, w \in L$ such that $v$ is a proper substring of ...
51 views

### what are all the ways of delimiting blocks

To my knowledge, in block-structured programming languages, there are 2, maybe 3 main ways of delimiting a block. Using start and end tokens, this can be brackets or reserved words etc Using ...
1 vote