字符串与子字符串前缀匹配算法Z-algorithm（比较难理解）

字符串与子字符串前缀匹配算法Z-algorithm（比较难理解）

问题

对于一个字符串s,设它的长度为len

z[i]所表示的是s[i…len-1]与s[0…len-1]的最长公共前缀

如何求出z[i]数组？

分析

这道题的解法是一个z算法，我也是第一次接触，O(n)的解法能够想到我觉得挺难的，需要通过已知的串s和z[1]…z[i-1]来求z[i]，

设想一个z数组，z[i]表示他的最长公共前缀即s[i]…s[i+z[i]].我们将其称之为i这个位置控制的范围，称为一个Z-box。我们定义l,r为右端点最靠右的Z-box的控制范围（即i和i+z[i]）。进行分类讨论

若i > r，则证明前面的所有Z-box和我们没有任何关联，我们无法利用，同时也证明i这个位置的Z-box一定是最靠右的，更新l=r=i，暴力匹配。若i < r，则令k=i-l，因为i位于Z-box内，则我们知道s[l]…s[r]应该与s[0]…s[r-l]匹配，所以此处的k对应的是i∈[l,r]这个位置在前缀即[0,r-l]中的对应位置，故我们可以根据z[k]的数值来计算我们的z[i]。令z[i]=min(z[k],r-i+1).Z-box在这里会有两种可能

(1)包含。k这个位置控制的Z-box的右端点并没有超过[l,r]这个Z-box的右端点，直接令z[i]=z[k]。(2)超过。k这个位置控制的Z-box的右端点超过了[l,r]对应的前缀。因为我们仅仅知道s[l]…s[r]与s[0]…s[r-l]匹配，后面的部分一概不知，所以我们令l=i，继续暴力匹配后面的长度，匹配完成后令z[i]=r-l即可。

这道题比较难理解，我也不是很懂，哈哈哈,对于z[i]为啥求最小值，举个例子：

s="aaaabaa"对于i=6的位置，r-i+1=1,Z[1]=3,但是不能把z[6]设置为3，因为显然不是，z[6]的初始化最大值是1，因为它的最大值不会超过r匹配的片段[l,r]，所以:z[i]=min(z[i-l],r-i+1)

代码一（暴力求解）

def z_naive(s): Z = [len(s)] for k in range(1, len(s)): n = 0 while n + k < len(s) and s[n] == s[n + k]: n += 1 Z.append(n) return Z

代码二 (Z算法)

def get_z(s): l=0 r=0 n=len(s) z=[0]*n for i in range(1,n): if(i>r): l=i r=i while(r

def get_z_v1(s): n=len(s) l=0 r=0 z=[0]*n for i in range(n): if(i<=r): z[i]=min(r-i+1,z[i-l]) while(i+z[i]r): l=i r=z[i]+i-1 return z

参考文献

[1].Z algorithm (Linear time pattern searching Algorithm). [2].Z algorithm. [3].Z-algorithm字符串匹配 算法小结. [4].Z-function and its calculation.https://cp-algorithms.com/string/z-function.html

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。