Z算法

chenxia25 · 2019-08-14 16:07:41 · 个人记录

Z算法

Z算法是一种用于字符串匹配的算法。此算法的核心在于z数组以及它的求法。

（以下约定字符串下标从1开始）

z数组和Z-box

定义z数组：z_{a,i}表示从字符串a的第i位开始，往后能与a的前缀匹配的最长长度。显然，z_{a,1}=|a|恒成立。

一个Z-box是一个区间。给定一个字符串a，那么a上存在一个Z-box[l,r]当且仅当满足以下全部条件：

通俗来说，若从a的第i位开始能与a的前缀匹配至少1位，那么能匹配的最长的串覆盖过的区间就是一个Z-box。（l\ne1是因为位置1很特殊，本身就是前缀，单独考虑）

例如若a=\texttt{acactaac}，那么z_{a}=[8,0,2,0,0,1,2,0]，Z-box有[3,4],[6,6],[7,8]。

z数组的求法

给定字符串a，现在我们需要求出z_{a}。

由于z_{a,1}的值不用求，而且位置1比较特殊，就是前缀，所以我们单独处理。

假设我们现在已经知道了z_{a,2\sim i-1}和使得zr最大的Z-box[zl,zr]，要求出z_{a,i}并更新zl,zr，那么分2种情况：

1. $i+z_{a,i'}\le zr$。显然$[i,i+z_{a,i'}]\subsetneq[zl,zr]$。根据Z-box的定义，$\forall j\in[i,i+z_{a,i'}],a_j=a_{j-zl+1}$。那么从$a$的第$i$位开始与$a$的前缀匹配的情况和从第$i'$位开始是一样的，直接令$z_{a,i}=z_{a,i'}$，$zl,zr$不变； 2. $i+z_{a,i'}>zr$。同理，$\forall j\in[i,zr],a_j=a_{j-zl+1}$。那么$a$的第$i\sim zr$位与$a$的前缀匹配的情况和第$i'\sim zr-zl+1$位是一样的，显然$z_{a,i}$至少有$zr-i+1$这么多，于是直接从第$zr+1$位开始暴力向后匹配求出$z_{a,i}$，并令$zl=i,zr=i+z_{a,i}-1$（因为$z_{a,i}$不可能为$0$）。

这样先令z_1=|a|，然后按上述方法从i=2递推到i=|a|，便可求出z_a数组。

下面是求z数组的代码：

//|a|=n
void z_init(){//求z数组
    z[1]=n;//特殊处理z[1]
    int zl=0,zr=0;//右端点最大的Z-box
    for(int i=2;i<=n;i++)//从i=2递推到i=n
        if(zr<i){//第1种情况
            z[i]=0;
            while(i+z[i]<=n&&a[i+z[i]]==a[1+z[i]])z[i]++;//直接向后暴力匹配
            if(z[i])zl=i,zr=i+z[i]-1;//更新右端点最大的Z-box
        }
        else if(i+z[i-zl+1]<=zr)z[i]=z[i-zl+1];//第2种情况的第1种情况
        else{//第2种情况的第1种情况
            z[i]=zr-i+1;//z[i]至少有zr-i+1这么多
            while(i+z[i]<=n&&a[i+z[i]]==a[1+z[i]])z[i]++;//后面再暴力匹配
            zl=i;zr=i+z[i]-1;//更新右端点最大的Z-box
        }
}

时间复杂度

按上述方法求z数组的时间复杂度是线性的\mathrm{O}(|a|)。

证明~~（感性）~~：观察上述方法可发现，只有当i>zr时，才可能将这个位置的字符与前缀匹配，而匹配结束后会把zr更新至最后一个匹配成功的位置，所以每个字符最多会和前缀成功匹配1次，所以匹配成功的总次数为\mathrm{O}(|a|)；算z_i时，如果往后暴力匹配（即遇到的不是第2种情况的第1种情况），那么第1次匹配失败就会停下来，所以匹配失败的总次数也为\mathrm{O}(|a|)。因此总时间就是匹配所花的时间\mathrm{O}(|a|+|a|)=\mathrm O(|a|)再加上一些赋值、更新zl,zr等一些1次只要\mathrm O(1)的操作，就还是\mathrm O(|a|)了。

Z算法的应用

Z算法和ExKMP算法是完全等价的，因为它们求的数组的意思是一样的。但是哈希、KMP能求的东西却有Z算法力所不及的。

Z算法最常用的用法就是字符串模式匹配（这个哈希和KMP也可以做到线性复杂度）。考虑把模式串b隔一个不常用字符接到文本串a前面，即令c=b+\texttt{!}+a。然后求出z_c，从i=|b|+2到i=|c|扫一遍，如果z_i=|b|，那么在该位置匹配成功。注意：所谓不常用字符一定不能在串中出现，不然会出bug。如果要用模式串c去匹配两个文本串a,b，可以令d=c+\texttt{!}+a+\texttt @+b，这时两个分隔符不能相同，不然也会出bug。

为什么Z算法在字符串模式匹配上花的时间和哈希相同呢？Z算法算出了从每一位开始能与前缀匹配的最长长度，但是字符串模式匹配只需要知道能否与前缀c_{1\sim|b|}匹配，并未完全使用z数组的价值。如果你就是想知道某一位开始能与前缀匹配的最长长度，哈希可就要二分的帮助了，复杂度是带\log的，不如用Z算法预处理一下。具体的可以参考下面3道例题。

不仅如此，Z算法的常数比哈希小（因为为了使哈希不被卡~~、不在CodeForces上FST~~，一般要写双重哈希），正确率也比哈希高（Z算法正确率当然是100\%啦）。

3道例题

CodeForces - 526D Om Nom and Necklace

题解传送门

CodeForces - 427D Match & Catch

题解传送门

CodeForces - 955D Scissors

题解传送门