输入：

有一个长字符串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,然后可以快速返回整个输入数组的最长长度后缀？