一个字符串中有多少个不同的子串？
How many different substrings are in a string?
我需要设计一个O(n)的算法，给定一个长度为n的字符串t，计算t的不同子串的个数。
为输入字符串建立一个后缀自动机。
求maxLength[v] - maxLength[suffixLink[v]] for all states v的和，其中maxLength[v]是根到v状态的最长路径，suffixLink[v]是后缀link 对于此状态。
在线性时间内构造后缀自动机是一个众所周知的问题。第二部分只是简单的遍历。因此，总时间复杂度为O(n).
我需要设计一个O(n)的算法，给定一个长度为n的字符串t，计算t的不同子串的个数。
为输入字符串建立一个后缀自动机。
求
maxLength[v] - maxLength[suffixLink[v]] for all states v的和，其中maxLength[v]是根到v状态的最长路径，suffixLink[v]是后缀link 对于此状态。
在线性时间内构造后缀自动机是一个众所周知的问题。第二部分只是简单的遍历。因此，总时间复杂度为O(n).