2
$\begingroup$

Consider the following problem. We are given a set of patterns (strings) $\Pi = \{\pi_i\}$, a text $s$, and a window length $k$. We want a list of all shifts $0 \le i \le |s|-k$ such that every pattern in $\Pi$ is contained in the substring $s[i:i+k]$.

Can this be solved in linear- or near-linear-time? It can of course be solved in quadratic time $O(|s| |\Pi| + \sum |\pi_i|)$ using KMP or Aho-Corasick plus post-processing.

The motivation for this problem is finding matches for a topic (represented by the set of patterns) in a text. In that context it actually makes sense to require the matches to be non-overlapping so I'm also interested in that case, but it might be easier to start with the relaxed version.

I would also be interested in generalizations of the problem that allow for approximate matches of some kind, eg, only requiring a threshold on the size of the subset of matching patterns, allowing matches within given edit distance, or something using hidden Markov models or general probabilistic graphical models. I would be surprised if any such generalization can be solved in subquadratic time though.

$\endgroup$
2
  • $\begingroup$ Can you be more precise about what you mean by linear time? Do you mean linear in $|s|$ (the length of $s$), without regard to the dependence on $k$ or $\Pi$? Or do you mean linear in $|s| + k + \sum_i |\pi_i|$? $\endgroup$
    – D.W.
    Aug 23, 2019 at 22:35
  • $\begingroup$ I had in mind "linear in the input size", so the latter, but I had not thought of the approach in your answer and I appreciate it. Thanks. For the practical problem I was looking to solve I think the $O(|s||\Pi| + \sum |\pi_i|)$ approach should be fast enough while exponential dependence on $k$ could be prohibitive. Was just wondering if it could be done faster. $\endgroup$
    – dysonsfrog
    Aug 24, 2019 at 0:08

2 Answers 2

1
$\begingroup$

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 times each pattern occurs inside the window, while it slides: increment the pattern’s count (and store where the occurrence begins) when detected by Aho-Corasick, decrement once the beginning is outside the window.

This should solve your problem in $\mathcal{O}(|s|+\sum{|\pi_i|})$

$\endgroup$
1
$\begingroup$

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 string $s$. You can then obtain all locations in the string where the DFA is in an accepting state; each such location is an index $i+k$ so that $s[i:i+k]$ matches all patterns in $\Pi$.

The running time will be linear in $|s|$ and the size of the DFA. I expect the size of the DFA to be exponential in $\Pi$ and $k$, but independent of $|s|$. So, if you only care about the dependence on $|s|$, this algorithm might meet your requirements. If you additionally care about the dependence on $\Pi$ and/or $k$, I do not expect this will meet your requirements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.