是否可以在 O(n) 中计算字符串中不同子串的数量？
Is it possible to count the number of distinct substrings in a string in O(n)?
给定一个长度为 n 的字符串 s，是否可以在 O(n) 中计算 s 中不同子串的数量？
例子
输入：abb
输出：5 ('abb', 'ab', 'bb', 'a', 'b')
我做了一些研究，但我似乎无法找到一种算法来如此有效地解决这个问题。我知道 O(n^2) 方法是可能的，但是有更有效的算法吗？
我不需要获取每个子字符串，只需要获取不同子字符串的总数（以防有所不同）。
构造LCP array并从子串数(n(n+1)/2)中减去它的和。
您可以使用 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的定义）；和
- 树中的字母与non-empty路径是一一对应的，因为：
- 每个不同的 non-empty 路径在其最后一个字母之后的不同位置结束；和
- 每个字母后面位置的路径是唯一的
对于想知道如何在 O(N) 时间内构建包含 O(N^2) 个字符的树的人们请注意：
后缀树的表示有一个技巧。不是将实际字符串存储在树的节点中，而是将指针存储到原始字符串中，因此包含 "abb" 的节点没有 "abb"，它具有 (0,3) - - 每个节点2个整数，不管每个节点中的字符串有多长，后缀树有O(N)个节点。
给定一个长度为 n 的字符串 s，是否可以在 O(n) 中计算 s 中不同子串的数量？
例子
输入：abb
输出：5 ('abb', 'ab', 'bb', 'a', 'b')
我做了一些研究，但我似乎无法找到一种算法来如此有效地解决这个问题。我知道 O(n^2) 方法是可能的，但是有更有效的算法吗？
我不需要获取每个子字符串，只需要获取不同子字符串的总数（以防有所不同）。
构造LCP array并从子串数(n(n+1)/2)中减去它的和。
您可以使用 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的定义）；和
- 树中的字母与non-empty路径是一一对应的，因为：
- 每个不同的 non-empty 路径在其最后一个字母之后的不同位置结束；和
- 每个字母后面位置的路径是唯一的
对于想知道如何在 O(N) 时间内构建包含 O(N^2) 个字符的树的人们请注意：
后缀树的表示有一个技巧。不是将实际字符串存储在树的节点中，而是将指针存储到原始字符串中，因此包含 "abb" 的节点没有 "abb"，它具有 (0,3) - - 每个节点2个整数，不管每个节点中的字符串有多长，后缀树有O(N)个节点。