8
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 length of mask, and find all matches in $O(n^2m)$ time. I'll show two solutions, one using dynamic programming and one using graph search. You can pick whichever ...
7
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}$. Now we are interested in substrings of size $n$ in new string $a$ that are orthogonal to $b$ (this is a very classic trick to deal with cyclic strings/arrays).
...
5
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 since they ignore either the size of the first array or the lengths of the strings.
Here are 2 different methods with their specific running times. The first of ...
5
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 run each string through the automaton - this takes $O(nm)$ time for running the strings through the automaton and $O(Mm)$ time for outputting the matches because ...
5
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 choice. Both have their strengths and weaknesses, but we found the Glushkov NFA quite economical and it maps very nicely to a bitwise implementation (the "LimEx"...
4
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$. consider the string $T=S*S'=AB*B'A$ where '*' is a character which doesn't appear in $S$.
As we can see, $A$ is a border of $T$. Conversely, if $X$ is a border of $T$,...
4
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 fairly-low-order bits:
10011000100101101000000
10110111000110110000000
It doesn't change the very lowest bits: Since $10 = 5\times 2$, the digit in position $k$ ...
4
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 weight to each edge.
The problem is solvable in polynomial time. An easy solution is to reduce the problem to minimum weight maximum matching. Create $b(v)$ ...
3
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, consider the suggestion in the comments, to consider some kind of distribution over words of length at most 20. In this case, string comparison is clearly $O(1)$...
2
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 are many other techniques for fuzzy matching, which you might want to investigate. The Levenshtein edit distance is only a starting point.
2
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 value that is small (like 3), as that may make some computations faster.
2
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 algorithm: follow the failure links until we find a position $j$ such that the letter at that position equals $b$.
Usually the failure link at the last letter is ...
2
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 long it takes to verify a match. Perhaps you are disregarding the time it takes to compute the hashes.
Ignoring all of this, let us suppose that we are ...
2
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 a letter from $A$.
All other letters are from $B$; in particular, " is not in $B$.
For simplicity, I identify $A$ and $B$ with the regular expressions $\sum_{\...
2
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 Expressions or Automaton Searching on Tries. Ricardo A. Baeza-Yates, Gaston H. Gonnet. Journal of the ACM, volume 43, number 6, 1996.
See also String ...
2
The Shortest Levenshtein's Distance should be good enough.
See if this Matching Wildcards Wikipedia page can be of help.
2
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 -> 3e8.
Also, consider the numbers $16^k-1$ and $16^k$. In hexadecimal, one is k f's, the other is 1 followed by k zeroes. Since $16^k$ in decimal doesn't end in ...
2
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 match). They denote $T[]$ where you use $LPS[]$
algorithm kmp_table:
input:
an array of characters, W (the word to be analyzed)
an ...
2
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. order["three"] = 3. Then your comparator for sorting two objects a and b in the input is order[a] <= order[b]
This way, you can easily abstract the pairwise comparisons. For example both Python and C++ (and probably many ...
2
Assuming the length of both arrays in your question is $\mathcal{O}(n)$, then in terms of required string comparisons:
Create an array of the form inverse = [("one", 1), ("two", 2), ("three", 3)] where the additional indices are the array indices and sort it lexicographically on the first pair elements. This can be done in $\mathcal{O}(n \ln n)$ string ...
1
Since the first symbol must match, we can just check it in the beginning, and solve the problem separately for each starting symbol (from here on, we just remove the starting letter from all strings).
First, let's start with without-trie intuition.
As an example, consider all permutations of string $abbc$. All possible strings are the following:
$$S=\{\cdot ...
1
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 by adding a start state which self-loops on any input and transitions to the next state on a match of the first character. Each subsequent state transitions ...
1
Since you want to detect all patterns at once, you can throw away any pattern if it is a substring of another one.
Since no pattern is a substring of another one, occurrences can neither begin nor end at the same position.
This means that when the window slides, at most one new occurrence appears and at most one disappears.
You can easily count how many ...
1
The set of all $k$-length strings that contain every pattern in $\Pi$ is regular; call it $L$. (It is $(\Sigma^* \pi_1 \Sigma^* \cap \dots \cap \Sigma^* \pi_m \Sigma^*) \cap \Sigma^k$.) From this, you can form a nondeterministic finite-state automaton (NFA) that recognizes $\Sigma^* L$. Next, convert this to a DFA. Finally, run the DFA across the input ...
1
What you are looking for is called the quasiperiod of a string. If such a string has a quasiperiod of $|S|$ it is called superprimitive, and can not be covered by a substring.
A method for computing it in $O(n)$ time is given in "An On-Line String Superprimitivity Test" by Dany Breslauer. You might also be interested in "Of Periods, Quasiperiods, ...
1
A proper prefix, which is also a suffix of the same string, is usually called border.
The condition you're asking about basically says this:
If $W[1..i-1]$ has a border of length $j$ and $W[j+1] = W[i]$, then $W[1..i]$ has a border of length $j+1$.
If $W[1..i-1]$ has no border of length $j$ such that $W[j+1] = W[i]$, then the length of the maximal border ...
1
One approach: Build a BK tree containing the terms in your term list. Given any word $w$, this lets you efficiently find the term that is closest to $w$ in Levenshtein edit distance.
Now the problem becomes easy. Do a linear scan over the document. For each word, look it up in the BK tree to find the closest match in your term list, and if it is close ...
1
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 will definitely still work, although you can easily build a hash collision. With a=123456791 you may need more time to build a hash collision, but they still ...
1
After mailing the author, I've found the answer:
The marking algorithm can be done in $O(B)$ by making sure that every unit of time we spend produces one mark. Consider the following piece of code:
for i in 1..|T|
for j in A s.t. T[i]==P[j]
m[i-j+1]++
The second loop need not take $O(|A|)$, it can be implemented more efficiently by precomputing the ...
1
You should look in the finite-automata literature for the terms 'Moore Machine' and 'Mealy Machine'. Comparing the two definitions will be instructive.
Only top voted, non community-wiki answers of a minimum length are eligible
