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

Hendrik Jan is correct about the Knuth-Morris-Pratt algorithm (warning, wikipedia doesn't explain it particularly well, a text on algorithms is probably a better bet). The failure function can be used to extract a DFA that can perform the string matching. It's not immediately obvious that the failure table is a DFA, but with very little work the transition ...


7

Create a temporary source string by concatenating itself together until the length of the source string is at least twice the length of the search string. The source string must be concatenated at least once. Then perform a simple (non-circular) search on that temporary string.


6

Here is the clean presentation (after going in circles around it). First you consider all substrings of S that are in M*. From that you build a trie, which may be understood as a tree structured FA that recognizes these substrings. You build it so that you complete first the transitions of nodes that are closest to the root. As soon as you have a node from ...


6

You can build a suffix tree in linear time and check if there's an inner node that corresponds to a full string (constant time per node). In more detail, assume we are given strings $s_1, \dots, s_n \in \Sigma^*$. Build a (generalised) suffix tree of $s_1\$_1, s_2\$_2, \dots, s_n\$_n$ with $n$ pairwise distinct terminal markers $\$_1,\dots,\$_n \notin \...


5

Given a FA $M$ accepting a language $L$, a suffix automaton is one which accepts the language of all suffixes of strings in $L$. In other words for a language $L$ over an alphabet $\Sigma$, $$ \operatorname{SUFFIX}(L)=\{y\mid\exists x\in\Sigma^* \ (xy\in L)\} $$ For example, if $L$ is the language denoted by the regex $ab^*a$ we'll have $L=\{aa, aba, abba, ...


5

Say that $F(n)$ occurs at some position if the substring starting at that position is compatible with either $F(n)$ or its complementation. How close can occurrences of $F(n)$ be? Take as an example $F(4) = abaab$. If $F(4)$ occurs at position $p$ then it cannot occur at position $p+1$ or $p+2$, but it can appear at position $p+3$. We let $\ell(n)$ be the ...


5

The problem is called substring search or string search or string matching. It's called a substring even if the elements of the array aren't characters. In this answer, I'll use character to refer to elements of the arrays, but this can be any kind of data (numbers, nested data structures, …). The standard terminology is: subset (without multiplicity): all ...


5

Answer. Although I have seen a deleted answer, I still think the construction is linear in the length of the string (considering the alphabet size constant). Aho Corasick 1975, doi:10.1145/360825.360855 Or perhaps KMP. Aho & Corasick consider pattern matching automata for a finite set of words, forming a tree with back-pointers in case of mismatches=...


5

Using Yuval's reduction, the problem can be reformulated as "Find the largest range $(i,j)$ in a binary string $S \in \{0,1\}^*$ such that the number of $1$s contained in the range is $\leq K$" (see this question). The idea is to start with an initial valid range $(0,j)$ of length $maxlen$ and then shift the "window" $(i,i+maxlen)$ to the right, checking at ...


5

One can reduce your problem to the following. Given a sequence of $N$ numbers, find a contiguous subsequence of length at most $K+1$ having maximal sum. This problem, in turn, is solvable in time $O(N)$. What's the connection between your problem and mine? Let the positions of the mistakes be $I_1,\ldots,I_t$, and add $I_0 = 0$, $I_{t+1} = N+1$. The ...


5

Suffix arrays can be used for this problem. They contain the starting positions of each suffix of the string sorted in lexicographic order. Even though they can be constructed naively in $O(n\log n)$ complexity, there are methods to construct them in $\Theta(n)$ complexity. See for example this and this. Let us call this suffix array SA. Once the suffix ...


4

Below is an expected $\mathcal{O}(n + m )$ algorithm (which can be extended to other $k$, making it $\mathcal{O}(nk +m )$). (I haven't done the calculations to prove it is so, though). The idea is similar to the Rabin-Karp rolling hash algorithm for exact substring matches. The idea is to separate each string of length $m$ into $2k$ blocks of $m/2k$ size ...


4

Sedgewick continues: "These are pattern characters that we know, so we can figure out ahead of time, for each possible mismatch position, the state where we need to restart the DFA." What I understand is that this quote tries to explain that if you encounter a mismatch at letter at position $j$ of the pattern you have to shift the patterns by one position ...


4

You can construct a suffix tree for that very large file and once generated the same can be used for querying. For Suffix tree generation use Suffix Array approach, there are many algorithm to generate suffix array. This is a taxonomy of many suffix array algorithm available today http://www.cas.mcmaster.ca/~bill/best/algorithms/07Taxonomy.pdf To starts ...


4

The answer is 66: any sequence of length greater than 66 must contain some repeated substring (as you argue in the question), and there exists a sequence of length 66 where no substring is repeated. The latter can be obtained from a de Bruijn sequence with $n=3$ and $k=4$. The length of this sequence is $k^n=64$ symbols. A de Bruijn sequence is a cyclic ...


4

This problem is called shortest superstring problem. John Gallant, David Maier and James Astorer proved it is NP-hard in 19791. Given two strings $A$ and $B$, let $|A|$ denote the length of $A$, and let $S(A,B)$ denote the shortest superstring of $A$ and $B$ where $A$ occurs before $B$. It is easy to reduce this problem to travelling salesman problem, ...


4

A trie is asymptotically optimal for this. No data structure can achieve better asymptotic running time. If you care about constant factors, the only way to know what will be optimal is to try multiple approaches and benchmark them. Standard theoretical running time analysis is not reliable at predicting constant factors. Another data structure to ...


3

Instead of a formal proof, I want to give some intuition behind the formula. The suffix array contains all the suffixes of the string $w$. A substring is nothing else than a prefix of a suffix. So if you count $\sum_i |S[i]|$, you will get all the substrings, but of course you overcount the number of different substrings. Let's have a closer look. Assume ...


3

Checking whether two 32-bit integers are equal can be done in a single machine instruction. Checking whether two strings are equal can take a lot longer. If my two strings are each 100 characters long, then checking whether those two strings are equal might require the equivalent of about 100 machine instructions: I have to check them, character by ...


3

Well these patterns will make KMP work faster: T=aaaaaaaaaa P=aaaa KMP will try 10 compare steps were Boyer-Moore will take 28 Another example: T=aaaaaaaaaa P=abab KMP will try 8 compare steps where BM will try 12.


3

There is a paper that did a good experiment over these string matching algorithms for different patterns: "Comparison of string matching algorithms: an aid to information content security" Also there is a study of these string matching algorithms for Japanese language: Comparison and Improvement of String Matching Algorithms For Japanese Texts I hope these ...


3

You are probably looking for the term n-grams, with $n = 2$ in your case. This is very useful in natural language processing and speech recognition.


3

It looks like you're missing the overlap case, if I understand your diagram correctly. This does the trick: A // goto B if read 0 else stay B // goto C if read 1 else stay C // goto D if read 1 else goto B D // goto E if read 0 else goto A E // emit rising edge, goto B assuming that you have a falling edge after every read.


3

You're looking for all instances of $Q$ as a substring of $T$, except that two symbols are still considered to match even if they differ by one, so this is basically a generalization of substring search (string matching). This particular problem can be solved efficiently using convolution methods. The running time will be something like $O(n \lg n)$, times ...


3

Yes, they mean the same thing. A n-gram is a sequence of n consecutive things (words, letters, whatever). A k-mer is a sequence of k consecutive things (DNA basepairs). The phrase k-mer is more common in computational genomics. See https://en.wikipedia.org/wiki/N-gram and https://en.wikipedia.org/wiki/K-mer for definitions.


3

You don't store the actual suffixes in the array. You only store indices, $n$ of them. Each index takes $O(1)$ space in the RAM model (which is what the textbook is using to count space), so in total the space consumption is $O(n)$. The number of bits used is $\Theta(n\log n)$.


3

To be blunt, the Stack Overflow question and its answers illustrate why you want to ask about such things here. The propsed algorithm clearly does not run in quadratic time. Since the length $n$ of the original string is our input size, and the length of the longest possible result string, we can not assume that string comparisons run in constant time. The ...


3

Here is a general solution for an alphabet of size $d \geq 3$ and a string of length $n$. Every string of length $n$ has $n-\ell+1$ substrings of length $\ell$. Hence the number of different substrings, of any length, is at most $$ \sum_{\ell=1}^n \min(n-\ell+1,d^\ell). $$ Consider now an infinite de Bruijn sequence, in which each prefix of size $d^r + r - ...


3

Let's denote $[\exists s: F(s) \wedge |s| = x]$ as $B(x)$. First property of $F$ implies that for any $x > L$ $$B(x) \implies B(x-1)$$ Which by induction implies: $$B(x) \implies \forall i \in [L, x] : B(i)$$ In other words, if you know that $B(x)$ is true, you don't have to examine lower values of $x$. And if $B(y)$ is false, you know that higher ...


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