是否可以在O(n)中计算字符串中不同子串的数量？

Question

给定一串s长度n,是否可以计算sO(n)中不同子串的数量？

例

输入: abb

输出:5('abb', 'ab', 'bb', 'a', 'b')

我做了一些研究,但我似乎无法找到一种能够以这种有效方式解决这个问题的算法.我知道O(n ^ 2)方法是可行的,但是有更高效的算法吗？

我不需要获得每个子串,只需要获得不同的子串(如果它有所不同).

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的子串和路径之间存在1-1对应关系(通过trie的定义); 和
• 树中的字母与非空路径之间存在1-1对应关系,因为:
  • 每个不同的非空路径在其最后一个字母后面的不同位置结束; 和
  • 每个字母后面的位置路径是唯一的

对于那些想知道如何在O(N)时间内构建包含O(N ^ 2)个字符的树的人的注意事项:

有一个后缀树表示的技巧.而不是存储在树的节点的实际字符串,你只储存指针到一部开拓创新的字符串,使包含节点"ABB"没有"ABB",它具有(0,3) - 每2个整数节点,无论每个节点中的字符串有多长,后缀树都有O(N)个节点.

Answer 2

构造LCP 数组并从子串数量 (n(n+1)/2) 中减去其总和。