# Tag Info

Accepted

### Find all substrings that fit the mask with asterisks

Yes, there is a more efficient algorithm. Your algorithm can take exponential time. You can check whether there exists any match in $O(nm)$ time, where $n$ is the length of text and $m$ is the ...
• 143k

### How to perform orthogonal check on two circular binary strings?

Say we have strings $a = a_0a_1...a_{n-1}$ and $b=b_0b_1...b_{n-1}$. First concatenate $a$ with itself and remove the last character. You should get a new string $a=a_0a_1...a_{n-1}a_0a_1...a_{n-2}$. ...
• 1,178

### Sorting array of strings (with repetitions) according to a given ordering

The other answers provide correct solutions. However, you can do a bit better considering multivariate complexity. Note that the provided running times in the other answers are not quite specific ...
• 4,093
Accepted

### Given a list of strings, find every pair $(x,y)$ where $x$ is a substring of $y$. Possible to do better than $O(n^2)$?

This can be solved with Aho-Corasick algorithm in $O(nm + Mm)$ time, where $M$ is the number of pairs outputted. First build the Aho-Corasick automaton for the set of strings in $O(nm)$ time. Then ...
• 1,319
Accepted

### NFA models with characters on nodes, not edges

Hyperscan chief architect here. The buzzword you are looking for is a Glushkov NFA, as opposed to a Thompson NFA. The 'traditional model' you refer to is a Thompson NFA but is by no means the only ...
Accepted

### KMP - longest palindromic prefix

KMP algorithm is able to solve your problem. Suppose your input string can be represented as $S=AB$ where $A$ is a palindrome ($B$ can be an empty string). Now reverse $S$ we can get $S'=B'A$. ...
• 258
Accepted

### By what criteria is the base value selected in Rabin Karp algorithm?

hash values, by definition, may collide this hash is computed (implicitly) by modulo of 2^N if you use N-bit integers recommended value of "a" is any large prime number, f.e. 123456791 With a=10, it ...
• 1,805

### By what criteria is the base value selected in Rabin Karp algorithm?

You can use any value you want, but it is best to choose a value that is relatively prime to the modulus, as that reduces the number of hash collisions. For efficiency you might want to choose a ...
• 143k
Accepted

### Streaming digit-to-digit conversion from decimal to hexadecimal

I don't think this is possible. Changing a high-order digit in a base-10 number -- say, changing 5000000 to 6000000 -- can change bits in its binary equivalent all the way from high-order bits to ...
• 5,164
Accepted

### one-to-many matching in bipartite graphs?

This problem is called the B-matching problem. Where you are given a function $b:V \rightarrow \mathbb{N}$ that assign a capacity to each vertex and a function $u:E \mapsto \mathbb{N}$ that assigns a ...
• 4,093
Accepted

### What is the expected time complexity of checking equality of two arbitrary strings?

In order to discuss the expected time complexity of an operation, you have to specify a distribution on the inputs, and also explain what you mean by $n$. One has to be careful, however. For example, ...
• 270k
Accepted

### Time complexity of Rabin-Karp algorithm

The running time you quote isn't correct. If $n = m$ then it takes $\Omega(n)$ to verify that $T = P$. The best case running time of any string matching algorithm is $\Omega(m)$, since this is how ...
• 270k

### The last failure link in KMP automaton

The link for position $i$ is not determined by the letter at position $i$ but instead by the letter $b$ at position $i-1$ (and the failure link at $i-1$). For the rest you correctly describe the ...
• 27.7k
Accepted

### Setting a cutoff for string distance filtering with different length strings

You can use normalized edit distance, where you divide the edit distance by the length of the larger of the two strings. Whether this is better will depend on what you are trying to achieve. There ...
• 143k
Accepted

### Regular expression for capturing a "C-style" string

Here is a regular expression for the set of all strings of the following form: They start and end with ". Every " in the middle must be escaped using a backslash. Every backslash must be followed by ...
• 270k
Accepted

### String matching

This problem was considered in the following papers: Partial-match retrieval algorithms. Ronald L. Rivest. SIAM Journal of Computing, volume 5, number 1, March 1976. Fast Text Searching for Regular ...
• 143k
Accepted

### reverse string to pattern matching

The Shortest Levenshtein's Distance should be good enough. See if this Matching Wildcards Wikipedia page can be of help.

### Streaming digit-to-digit conversion from decimal to hexadecimal

You can't do this - if you don't know whether the input is k digits or k+1 digits, then the additional decimal digit changes all or most of the hexadecimal digits. For example 100 -> 64, but 1000 -> ...
• 25.5k
Accepted

### Time complexity for calculating the $LPS$ array (failure function) in KMP algorithm preprocessing

I've copied below the wikipedia algorithm for computing the LPS array (which is usually called the failure function because in the main KMP algorithm you refer to this table whenver there's a failed ...
• 464

### Sorting array of strings (with repetitions) according to a given ordering

I think a straightforward way to accomplish this would be to create a mapping of every element in your ordering list to its index i.e. ...
• 967
Accepted

### What is the SetHorspool string searching algorithm and how is it implemented?

Reading the source code we can see that it is an extension of Horspool to find a match from a set of needle strings $S$, rather than matching a single needle string. How it works is by representing ...
• 12.4k
Accepted

### Find optimal local alignment of two strings with restrictions

Compute the optimal local alignment score OPT of both strings in $O(mn)$ time and $O(n)$ space by maintaining just a single row of the DP matrix. (Since we are only computing the score and don't need ...
• 5,164

### What are string matching algorithms used in text editors like Atom and sublime

Since Emacs is the superior editor, you can take a look in the source code yourself: search.c Emacs uses the Boyer–Moore string-search algorithm, so that's probably what you should prefer too.
• 13.3k
Accepted

### Finding which strings in a set of strings have a certain prefix - can it be smaller than O(number of strings*length of prefix)

In the worst case, it has to be $n \cdot d$: You must check $d$ symbols of each of the $n$ strings to confirm they all start with the prefix, if you leave any out it might be different. This is ...
• 13.7k

The failure link at a certain position $k$ in the string points to the longest prefix of the string which is also a suffix of the string before the position $k$. The first observation we need is that ...
• 27.7k
Accepted

### How to match a string with any linear transformation of the pattern?

Your idea of extracting the ratios of successive differences between the adjacent numbers is brilliant. Let $P''$ retain all needed information The $0$'s in $P'$ or $T'$ pose some difficulty in ...
• 34.9k
Accepted

### Complexity of string comparison vs whitespace-trimmed string comparison

From the viewpoint of complexity theory, comparing two strings, with or without surrounding whitespace, takes time linear in the lengths of the strings, because there is no computational model, ...
• 11.3k
1 vote

### What is the expected time complexity of checking equality of two arbitrary strings?

In addition to what was said before, consider a modern version of "string" that is fully Unicode compatible. Which means a string is a sequence of Unicode code points, and you can't just ...
• 25.5k
1 vote

### Find first occurence of multiple tokens using C++

You can turn that search into a DFA,and you can then pass the input through the DFA until an accepting state is reached (or the end of the string is encountered). Each pattern is turned into an NFA ...
• 11.3k

Only top scored, non community-wiki answers of a minimum length are eligible