8
votes
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 ...
D.W.♦
- 143k
7
votes
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
5
votes
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
5
votes
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
5
votes
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 ...
4
votes
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
4
votes
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
4
votes
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 ...
D.W.♦
- 143k
4
votes
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
4
votes
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
3
votes
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
2
votes
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
2
votes
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
2
votes
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 ...
D.W.♦
- 143k
2
votes
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
2
votes
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 ...
D.W.♦
- 143k
2
votes
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.
2
votes
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
2
votes
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
2
votes
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
2
votes
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
2
votes
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
2
votes
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
2
votes
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
2
votes
please help me understand the algorithm for building the KMP failure function
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
2
votes
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
2
votes
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