# Given a list of strings, find every pair $(x,y)$ where $x$ is a substring of $y$. Possible to do better than $O(n^2)$?

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

• 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. – John L. Jan 26 '20 at 23:53
• 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). – Aaron Rotenberg Jan 27 '20 at 0:18
• 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. – Aaron Rotenberg Jan 27 '20 at 0:27
• @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)$? – John L. Jan 27 '20 at 1:25
• 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? – securitymensch Jan 27 '20 at 10:59

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:
• 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. – Pseudonym Jan 28 '20 at 3:50