给定一个字符串列表，找到每对 $(x,y)$，其中 $x$ 是 $y$ 的子字符串。有可能比 $O(n^2)$ 做得更好吗？

Question

考虑以下算法问题：给定一个字符串列表 $L = [s_1, s_2, \点, s_n]$, ，我们想知道所有对 $(x,y)$ 在哪里 $x$ 是一个子串 $y$. 。我们可以假设所有字符串的长度都是最大的 $百万$, ， 在哪里 $m << n$ 并且都在有限的字母表上 $\西格玛$ 和 $|\西格玛|<< n$. 。我们还可以假设对的数量 $(x,y)$ 在哪里 $x$ 是一个子串 $y$ 远小于 $n$.

一个简单的算法是这样的：

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

然而，这有复杂性 $O(n^2 \cdot m)$ - 我很好奇是否有更快的算法？

编辑:正如评论中指出的，最多可以有 $n^2$ 这样的对，所以我不明白如何有一个算法比 $O(n^2)$. 。但是，我想知道是否有类似的东西 $P-FPT$ 算法，其中平方复杂度取决于输出对的数量，而不是 $n$？或者至少有一种算法可以将复杂性降低到比 $O(n^2 \cdot m)$.

Answer 1

这可以解决 Aho-Corasick 算法 在 $O(纳米 + 毫米)$ 时间、地点 $M$ 是输出的对的数量。

首先为中的字符串集构建 Aho-Corasick 自动机 $O(纳米)$ 时间。然后通过自动机运行每个字符串 - 这需要 $O(纳米)$ 通过自动机运行字符串的时间和 $O(毫米)$ 输出匹配的时间，因为相同的字符串可以匹配 $百万$ 最坏情况下的次数。（例如 ab 火柴 ababab 3次。）

---

这可以改进为真正的线性 $O(L + M)$ 时间、地点 $L$ 是字符串的总长度， $M$ 是匹配数：

当通过自动机运行字符串时，为自动机的每个节点存储访问该节点的前一个字符串的索引。输出匹配时，如果链接指向已访问过该字符串的节点，请停止跟踪字典链接 - 您已经输出了从该节点向上的所有匹配。现在每个匹配只输出一次，并且仅当输出新匹配时我们才遍历字典链接。