KMP算法和Z算法之间的关系

Question

KMP和Z算法是用于字符串搜索的众所周知的算法，

KMP算法处理通过KMP失败函数查找模式，该函数定义为（pat是搜索模式）

lps [i] = pat [0..i]的最长适当前缀，也是pat [0..i]的后缀。

例如，用于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]。

Answer 1

注意：算法错误

for i in range(0, len(s)):
    if lps[i] != 0:
        Z[i - lps[i] + 1] = lps[i]

之后 inZ[i]将是后缀的最大长度，从位置开始i，也是字符串的前缀。

编辑

正如 nikhil_vyas 指出的，所提出的算法不能解决您的问题。它实际上所做的是Z用最长的后缀和其他一些后缀部分填充数组。这样的不完整数组基本上可以帮助你解决几个“找到字符串中最长的东西”问题，但它并不能回答你的问题。

Z我想到的重建数组的最简单方法lps是构建与该lps数组相对应的字符串，然后Z为该字符串构建数组。但我不确定它是否符合您对“lps数组中的某些修改”的定义。