3
$\begingroup$

Consider the following algorithmic problem: Given a list of strings $L = [s_1, s_2, \dots, s_n]$, we want to know all pairs $(x,y)$ where $x$ is a substring of $y$. We can assume all strings are of length at maximum $m$, where $m << n$ and are all over a finite alphabet $\Sigma$ with $|\Sigma| << n$. We may also assume that the number of pairs $(x,y)$ where $x$ is a sub-string of $y$ is much smaller than $n$.

A trivial algorithm would be this:

1. foreach x in L:
2.   foreach y in L:
3.      if x is substring of y:
4.         OUTPUT x,y

However, this has complexity $O(n^2 \cdot m)$ - I am curious to know whether there is a faster algorithm?

Edit: As pointed out in the comments, there can be at most $n^2$ such pairs, so I don't see how there can be an algorithm faster than $O(n^2)$. However, I was wondering if there is something like a $P-FPT$ algorithm where the squared complexity is dependent on the number of output pairs, rather than $n$? Or at least an algorithm that reduces the complexity to something better than $O(n^2 \cdot m)$.

$\endgroup$
5
  • 1
    $\begingroup$ Consider $s_1=$ "a" and $s_2$ is a string of length $n^3$. Can you tell me how much it takes to determine whether $s_1$ is a substring of $s_2$? It looks like $O(n^3)$ to me. What I mean is that your question might become trivial without some proper restrictions. I would recommend that you add some condition, such as the length of every string is $o(n)$ uniformly with finite alphabet. $\endgroup$
    – John L.
    Jan 26, 2020 at 23:53
  • $\begingroup$ Yeah, I think the comment by @JohnL makes sense. You might want to add an $m$ parameter for the maximum string length and write your algorithm's complexity as $O(n^2m)$ (assuming KMP string matching). $\endgroup$ Jan 27, 2020 at 0:18
  • $\begingroup$ If you just need to count the matching pairs, I think you can do this efficiently with a KMP-style automata-based algorithm. Basically, you do one pass where you construct a count-annotated DFA that accepts a string if it is a substring of one of the input strings, then a second pass where you run each string through the DFA and total the annotations. Not sure enough yet on the details to post an answer. $\endgroup$ Jan 27, 2020 at 0:27
  • $\begingroup$ @securitymensch, the number of substring pairs can be as great as $\Theta(n^2)$. Suppose we do know all those pairs. Do you have a well-defined reasonable computation model where you can specify all those pairs faster than $O(n^2)$? $\endgroup$
    – John L.
    Jan 27, 2020 at 1:25
  • $\begingroup$ Thanks for the comments, I am sorry that the question missed important details. I edited the question and tried to clarify the details. @JohnL. Given your comment, I don't see any possibility to be faster than $O(n^2)$. However, maybe something like an $P-FPT$ algorithm would be possible? $\endgroup$ Jan 27, 2020 at 10:59

1 Answer 1

5
$\begingroup$

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 the same string can match $m$ times in the worst case. (For example ab matches ababab 3 times.)


This can be improved to true linear $O(L + M)$ time, where $L$ is the total length of the strings and $M$ is the number of matches:

When running the strings through the automaton, store for each node of the automaton the index of the previous string for which this node was visited. When outputting the matches, stop following the dictionary links if the link leads to a node that has already been visited for this string - you have already outputted all matches that are upwards from that node. Now each match gets outputted exactly once, and we traverse dictionary links only when new matches are outputted.

$\endgroup$
1
  • $\begingroup$ Nice! There's also an obvious $O(mn+Mm)$-time algorithm using suffix trees, incidentally, which I think ticks all the boxes: build a suffix tree, then do a pattern search on all the input strings, discarding the one that is equal to the original string. Suffix trees are more general than the Aho-Corasick automaton, so it's possible that there's an even more efficient algorithm to be found using that. $\endgroup$
    – Pseudonym
    Jan 28, 2020 at 3:50

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.