New answers tagged


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 ...


It is a shortest superstring problem and not allowing internal substrings is just an implementation detail.


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 ...


To improve your brute force, you would only need to look at the substrings of minimum length, as longer substrings will occur at most as many times as their own substrings. This should take linear time to create the dictionary, and O(nlog(n)) to sort. If this is too memory intensive, you could do pruning by first brute-forcing this for say, substrings of ...

Top 50 recent answers are included