7

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

KMP算法处理通过定义为（pat作为搜索模式）的 KMP 失效函数来查找模式

lps[i] = pat[0..i] 的最长专有前缀，它也是 pat[0..i] 的后缀。

例如因为string "abcab"它会是[0, 0, 0, 1, 2]

其中 asZ算法使用定义为的 z 函数：

给定一个长度为 n 的字符串 S，Z 算法生成一个数组 Z，其中 Z[i] 是从 pat[i] 开始的最长子字符串的长度，它也是 pat 的前缀。

现在的问题是我们可以Z通过使用KMP算法来实现这个功能吗？我正在搜索的是lps数组中的一些修改，这些修改导致与数组相同的结果Z[i]。

4

3 回答 3

3

注意：算法错误

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具有数组的数组的最简单方法是构建字符串，对应于数组，然后为该字符串构建数组。但我不确定它是否适合您对“数组中的一些修改”的定义。lpslpsZlps

于 2013-09-17T14:36:43.190 回答
1

我认为这会做到。

def Z(lps):
    # First assume that we always need to restart when we find a mismatch.
    Z = [0] * len(lps)

    # Step through adjacent pairs.
    itr = enumerate(zip(lps, lps[1:]), start=1)
    for i, (prev, cur) in itr:
        if cur <= prev: # suffix stopped growing
            Z[i - prev] = prev # Mark this suffix at its beginning.

    # Ending the string is also a way to stop growing the suffix.
    if cur > 0: # if we were still growing a suffix
        # At end of loop, cur is the new prev, and i+1 is the new i.
        # (i == len(lps) - 1, cur == lps[-1])
        Z[i+1 - cur] = cur

    return Z

样品：

Z([0,0,0,1,2]) #=> [0,0,0,2,0]
Z([0,0,1,2,1,2]) #=> [0,0,2,0,2,0]
于 2015-10-24T06:53:21.933 回答
0

Mikhail Melnik 的解决方案可能不会为像“aaaaa”这样的字符串中的所有索引计算 Z，我们需要额外的迭代来填充在第一次迭代中留空的索引。

for i in range(0, len(s)):
    Z[i - lps[i] + 1] = lps[i]
for i in range(0, len(s)):
    Z[i] = max(Z[i], Z[i - 1] - 1)                     `
于 2015-06-19T17:04:17.753 回答