java – 查找String和String前缀之间最长后缀长度的算法

发布时间：2020-12-15 01:03:52 所属栏目：Java 来源：网络整理

导读：输入：有一个长字符串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] 样本输出：输出[] =

输入：

有一个长字符串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))

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!