Suppose we are given a collection of $n$ strings, $S_1,\dots,S_n$. I would like to know whether any of those strings is a substring of any other string in the collection. In other words, I'd like an algorithm for the following task:
Output: $i,j$ such that $S_i$ is a substring of $S_j$ and $i\ne j$, or None if no such $i,j$ exist
Is there an efficient algorithm for this?
If we replace "substring" with "prefix", there is an efficient algorithm (sort the strings, then do a linear scan to compare adjacent strings; sorting will ensure that substrings are adjacent). But it seems more challenging to test whether any string is a substring of any other string. A naive algorithm is to iterate over all pairs $i,j$, but this requires $\Theta(n^2)$ substring tests. Is there a more efficient algorithm?
I guess we could call this "all-pairs substring testing", or something like that.
My ultimate goal is to prune the collection so no string is a substring of any other, by removing each one that is a substring of something else in the collection.