string - KMP算法与Z算法的关系

Question

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

KMP 算法通过定义为(pat 是搜索模式)的 KMP 失败函数处理寻找模式

lps[i] = the longest proper prefix of pat[0..i] which is also a suffix of pat[0..i].

例如对于 string "abcab" 它将是 [0, 0, 0, 1, 2]

Z 算法使用 z 函数定义为:

Given a string S of length n, the Z Algorithm produces an array Z where Z[i] is the length of the longest substring starting from pat[i] which is also a prefix of pat.

现在的问题是，能否利用KMP算法来实现Z的功能呢？ 我正在搜索的是 lps 数组中的一些修改，这些修改导致与 Z[i] 数组相同的结果。

Answer 1

注意:算法错误

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

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

编辑

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

我想到的重建具有lps 数组的Z 数组的最简单方法是构建对应于lps 数组的字符串然后为该字符串构建 Z 数组。但我不确定它是否符合你对“lps array 中的一些修改”的定义。