People who code: we want your input. Take the Survey

# Tag Info

5

There are various algorithms for pattern matching in string. Exact String matching algorithms Brute Force Rabin Karp Boyer-Moree KMP Aho Corasick etc. Approximate String Matching Algorithm Approximate String matching is applied in text searching, pattern recognition and signal processing applications. For a text T[1..n] and pattern P[1...m], we are ...

5

You could append all of the $n$ strings together, and add an arbitrary character '\$' not in the pattern to separate them. Then you could apply the Z algorithm on your original pattern and this new string to yield time complexity$O(nl+k)$which is more efficient than your suggested$O(nl+nk)$. Actually, you could still iterate with KMP for$O(nl+k)$time, ... 4 You can use a suffix tree, which is a compressed trie that allows you to store all possible suffixes from the strings in$S$. To search for a substring$q$, you can simply traverse the suffix tree from the root1 to the leaves, making comparisons with the edge keys (each of which represents one or more characters). If a branch does not exist in the tree, then ... 3 Both - attempt 1 and 2 - are incorrect executions of the Horspool's algorithm. After the first round of trying to match the pattern in the text: 001001001001 111 There are two comparisons made of which the second one 0 == 1 fails. Now, the shift is determined by the last character in the section of the text being matched i.e. shift value of 1 which is 1. ... 2 Your algorithm is not correct. Consider 21: 21 = [(2, 1), (21)] First we find 2 in (1-9): 123456789. However, a 3 follows, so it's not a solution. Then we try to find 21 in (10-99). This finds a solution, but it's 21. However there is an earlier solution: 123456789101112131415161718192021 So the solution is not correct. The sequence you're after is ... 2 Assume that you build an automaton for finding occurrences of$bububa$in the input string. When the automaton reads the input string$bubububa$, then it after reading$bububu$, it must not just return to state$\epsilon$, as otherwise an occurrence of$bububa$is not detected. Also, jumping back to state$bu$is would not do the trick, as then again, the$...

2

The implementation provided in Wikipedia is $O(n^2)$. But these tables can actually be built in $O(n)$ time via Z-algorithm. Since you can find Z-algorithm on internet easily, I just provide a sketch here. Let $s[i,j]$ denote the substring of $s$ from $i$-th position to $j$-th position. Like what we see in the $O(n^2)$ code, we want to find the largest ...

2

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 the set $S$ as a trie. This allows you to efficiently check character by character whether starting at position $i$ any of the strings on the trie can be found in ...

2

No one knows. It is believed to be computationally infeasible to find such a string, if one exists. No one knows whether such a string exists. By standard heuristics (modelling SHA256 as a random function), there is approximately a $1/e\approx 0.368$ chance that no such input exists, and approximately a $0.632$ chance that such an input exists, so if I ...

2

The answer depends on the number of patterns, the total size of the strings $nl$, and how many times you expect the pattern to occur in each string. If you have a few patterns, a standard string matching algorithm such as KMP is sufficient. If you have many patterns at the same time, you should use an algorithm that preprocesses the patterns (e.g. Aho-...

2

The "information-theoretic lower bound" that you mention here is correct if you are encoding an element of a set, all of whose elements should be considered equiprobable. That doesn't really apply to this problem. It's true that you could encode each character name as though it was a random element of the set of strings of length between 2 and 38 ...

1

The shift rules of Boyer–Moore algorithm come from the bad character rule and the good suffix rule. While the bad character rule exploits a single character that is in the text but not in the pattern, the good suffix rule exploits multiple contiguous characters that appear in both the text and the pattern. "In the first table, for k = 5, we have d2 = 4.&...

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

I don't think an $\mathcal{O}(1)$ solution can be possible, since if nothing else, you need to examine all digits of your input. But if n is the number of digits in your input (such that the numerical value of your input is between $10^{n-1}$ and $10^n$), there's definitely a polynomial-time solution in n, whereas the substring–based approaches (that ...

1

The algorithm is based on a simple principle. Suppose that we are trying to match a substring of length n. We are going to first look at character at index m. If that character is not in the string, we know that the substring we want can't start in characters at indices 1 2....n If that character is in our string, we will assume that it is at the last place ...

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