输入：
有一个长字符串S,我们有一个整数数组A表示字符串S的前缀,如A [i]表示前缀S [0..A [i]]
输出：
返回一个与A大小相同的数组Output [],其中Output [i]是S [0..A [i]]和S的最长匹配后缀的长度
样本输入：
S = "ababa"
A[]=[0,1,2,3,4]
样本输出：
输出[] = [1,5]
我所拥有的最天真的算法是每个A [i]只匹配两个字符串末尾的S [0..A [i]]和S之间的字符数.但是这个算法是O(n ^ 2),其中n是原始String S的长度.
题：
是否有更好的算法预处理字符串S,然后可以快速返回整个输入数组的最长长度后缀？
最佳答案
这只是反向弦的Z-function.稍有不同的是,Z函数的第一个元素被选择为等于S的长度.有一个算法来计算O(n)中字符串的Z函数
并且该问题的算法如下：
> S’：=反转S.
> Z：= S’的Z函数
>对于每个i,输出[i]：= Z [Len(S) – A [i] – 1]
例如：
S = "baabaaa"
A[] = [0,4,5,6]
Output[] should be [0,7]
S' = "aaabaab"
Z = Z-function(S') = [7,0] (with the first element chosen to be Len(S))
