【算法】字符串匹配之Z算法

时间:2022-03-03 10:39:38

求文本与单模式串匹配,通常会使用KMP算法。后来接触到了Z算法,感觉Z算法也相当精妙。在以前的博文中也有过用Z算法来解决字符串匹配的题目。

下面介绍一下Z算法。

先一句话讲清楚Z算法能求什么东西。

输入为一个字符串s,Z算法可以求出这个字符串每一个后缀与自身的最长公共前缀LCP,Z算法可以求出一个数组z,z[i]表示suffix(i)与字符串本身的最长公共前缀。

接下来,介绍Z算法的具体内容。

记字符串s的长度为n。

Z算法需要维护一对值,记为left和right,简记为L和R。L和R满足s[L,R]为s串的前缀。当i为1的时候,暴力比较s[0,n-1]与s[1,n-1]可得此时的L与R,同时也得到了z[1],即suffix(1)与s本身的LCP。

假设计算至i-1,我们已经得到了当前的L与R,同时也得到了z[1]到z[i-1]的值,现在需要计算z[i]与新的L和R。

1.假设i>R,则说明不存在一个结束于i或者i之后的串,同时这个串本身也为s的一个前缀,否则R不应该小于i。对于这种情况,需要重新计算新的L与R,令L=R=i,暴力比较s与suffix(i),得到z[i]=R-i+1=R-L+1。

2.此时i<=R,令k=i-L,可以断言z[i]>=min(z[k],R-i+1)。因为根据L与R的含义,此时我们可以将L到R视作为字符串的前缀,那么i相对于L的偏移量为k。

如果z[k]<R-i+1,则z[i]必然等于z[k],基于此时,s[k,k+z[k]-1]是s[i,R]的一个前缀,同时在这种情况下L与R不变。

如果z[k]>=R-i+1,根据R的含义可知s[R+1]!=s[R-L+1],z[k]中大于R-i+1的匹配信息因为s[R+1]!=s[R-L+1]而无效,但这并不意味着s[R+1]!=s[R-i+1],此时根据z[k]可以断言z[i]至少是R-i+1,是否可以更大需要再进行计算,令L=i,更新R值,并得到此时的z[i]。

 

具体实现中,第二种情况的两种子情况可以归一化处理。

 

给出一个C++实现代码:

【算法】字符串匹配之Z算法【算法】字符串匹配之Z算法
 1 void Z(char *s,int n=0) {
2 n=(n==0)?strlen(s):n;
3 z[0]=n;
4 int l=0,r=0;
5 for (int i=1;i<n;i++) {
6 if (i>r) {
7 l=i,r=i;
8 while (r<n&&s[r-i]==s[r]) r++;
9 z[i]=r-l;
10 r--;
11 }
12 else {
13 int k=i-l;
14 if (z[k]<r-i+1)
15 z[i]=z[k];
16 else {
17 l=i;
18 while (r<n&&s[r-i]==s[r]) r++;
19 z[i]=r-l;
20 r--;
21 }
22 }
23 }
24 }
View Code

 

过程中每个字符至多被L和R扫到一次,Z算法是线性的复杂度。

Z算法解决单模式串匹配的方法很简单,令S为文本串,T为模式串,构造新串P=T+'#'+S,计算z数组,从S在P中开始的位置向后扫描,如果z[i]=length(S),则说明此处有一个匹配。当然其实也可以不加'#',那样子的话判断需要用>=而不是=。相较于KMP,对于解决单模式串匹配,如求所有匹配位置,其实用Z算法求的话是可以做到不用额外空间的(对于字符串拼接,可以不用开一个新的字符串。过程中判断匹配即可,不必保存z数组。),而KMP的话,不保存模式串的next数组,是没办法进行匹配运算的。