KMP and Z算法是众所周知的字符串搜索算法，
KMP算法通过 KMP 失效函数寻找模式，该函数定义为 (pat是搜索模式）
lps[i] = pat[0..i] 的最长真前缀，也是 pat[0..i] 的后缀。
e.g for string "abcab"这将是[0, 0, 0, 1, 2]
然而Z算法使用 z 函数，定义为：
给定长度为 n 的字符串 S，Z 算法会生成一个数组 Z，其中 Z[i] 是从 pat[i] 开始的最长子字符串的长度，pat[i] 也是 pat 的前缀。
现在的问题是我们能否实现Z功能通过使用KMP算法？
我正在寻找的是一些修改lps导致与相同结果的数组Z[i] array.
注意：算法错误
for i in range(0, len(s)):
if lps[i] != 0:
Z[i - lps[i] + 1] = lps[i]
之后在Z[i]将是后缀的最大长度，从位置开始i这也是字符串的前缀。
EDIT
正如 nikhil_vyas 指出的，所提出的算法不能解决您的问题。它实际上所做的是部分填充Z具有最长后缀和其他一些后缀的数组。这样的不完整数组基本上可以帮助你解决几个“找到字符串中最长的东西”问题，但它并不能回答你的问题。
最简单的重建方法Z数组有lps我想到的数组是构建字符串，对应于lps数组，然后构建Z该字符串的数组。但我不确定它是否符合你对“某些修改”的定义lps array".
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
