KMP算法与Z算法的关系
KMP算法与Z算法的关系
提问于 2013-08-29 21:34:02
KMP和Z算法是著名的字符串搜索算法，
KMP算法处理通过KMP故障函数(pat是搜索模式)查找模式的问题。
lpsi =pat0.i的最长的适当前缀，它也是pat0.i的后缀。
例如，对于string "abcab"，它将是[0, 0, 0, 1, 2]
其中，as Z算法使用z函数，定义为：
给定长度为n的字符串S，Z算法产生数组Z，其中Zi是从pati开始的最长子字符串的长度，pati也是pat的前缀。
现在的问题是，我们能否使用Z算法实现KMP函数？我正在搜索的是lps数组中的一些修改，这些修改将导致与Z[i]数组相同的结果。
回答 2
Stack Overflow用户
发布于 2015-10-24 06:53:21
我想这样就行了。
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]Stack Overflow用户
发布于 2015-06-19 17:04:17
Mikhail的解决方案可能不会计算像"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) `页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/18521337
复制相关文章
相似问题
腾讯云开发者
