有没有可能在O(n)的时间内计算一个字符串中不同子串的数量？

Question

给定一个长度为 n 的字符串 s，是否有可能在 O(n) 的时间复杂度下计算 s 中不同子串的数量？

示例：

输入：abb

输出：5（'abb'、'ab'、'bb'、'a'、'b'）

我已经进行了一些研究，但似乎找不到一种解决这个问题的高效算法。我知道 O(n^2) 的方法是可行的，但是否有更有效的算法？

我不需要获取每个子串，只需获取不同子串的总数（如果有区别的话）。

- donrondon

---

'ba' 不是 'abb' 的子字符串。 - gnasher729

@gnasher729 你是对的，有人已经编辑过了。 - donrondon

我认为这个问题应该在这里提出：https://cs.stackexchange.com/ - ChaosPredictor

Answer 1

你可以使用Ukkonen算法在线性时间内构建后缀树：

https://en.wikipedia.org/wiki/Ukkonen%27s_algorithm

s的子串数量等于trie中字符串前缀的数量，你可以在线性时间内简单地计算出来。它就是所有节点中字符的总数。

例如，你的示例生成了一个后缀树，如下所示：

            /\                
           b  a
           |  b
           b  b

树中有5个字符，因此有5个子字符串。每个唯一的字符串都是从根节点开始以不同字母结尾的路径: abb、ab、a、bb、b。因此，字符串的数量就是树中字母的数量。

更准确地说:

- 每个子字符串都是某个字符串后缀的前缀; - 所有后缀都在Trie中; - 因此，在Trie上存在子字符串和路径之间的一一对应关系（根据Trie的定义）; 并且 - 树中的字母与非空路径之间存在一一对应关系，因为：

- 每个不同的非空路径在其最后一个字母后面结束于不同的位置; 和 - 到达每个字母后面的位置的路径是唯一的。

注意：对于那些想知道如何在O（N）时间内构建包含O（N ^ 2）个字符的树的人，请看这里。

表示后缀树的技巧在于，不要将实际字符串存储在树的节点中，而是仅存储指向原始字符串的指针。因此，包含“abb”的节点并没有“abb”，而是有(0,3)——每个节点只有2个整数，无论每个节点中的字符串有多长，后缀树具有O(N)个节点。

- Matt Timmermans

---

谢谢你的回答。你提到的维基百科文章说，Ukkonen算法可以在O(n)时间内完成，但仅适用于常量大小的字母表，这是什么意思？此外，我不明白为什么s的子字符串数量是“Ukkonen结果树中所有节点的字符总数”。 - donrondon

“常量大小的字母表”意味着字符串中可供选择的字符数量有限，例如26个字母、256个字节或65536个字符等。另一种选择是针对无限字母表的后缀树，例如任意无界整数序列。 - Matt Timmermans

我在回答你的另一个问题时添加了一些解释。 - Matt Timmermans

我很感激你的努力，现在更清晰了。已标记为最佳答案。 - donrondon

@MattTimmermans 举个例子，假设我的原始字符串是 s="abbabbab"。那么，请问您将在节点中存储什么（以获得O(n)时间复杂度），并如何确保不重复计算相同的子字符串？ - Nannan AV

Answer 2

构建LCP数组并将其总和从子字符串的数量（n（n+1）/2）中减去。

- David Eisenstat

---

你能解释一下如何在O(n)时间内构建LCP数组吗？我找到了一些相关信息，但是有点迷惑。 - donrondon

@donrondon 你有后缀树吗？ - David Eisenstat

我知道如何用O(n^2)构建一个，但不知道如何用O(n)构建。 - donrondon

我们可以在O(nlogn)的时间复杂度内构建LCP数组。详情请参考http://www.geeksforgeeks.org/­­kasais-algorithm-for-construction-of-lcp-array-from-suffix-array/。 - pavaniiitn