Z算法

z算法

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

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

\(\bm z\)数组和z-box

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

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

• \(l\ne1\)；
• \(z_{a,l}\ne0\)；
• \(r=l+z_{a,l}-1\)。

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

例如若\(a=``\text{acactaac''}\)，那么\(z_{a}=[8,0,2,0,0,1,2,0]\)，z-box有\([3,4],[6,6],[7,8]\)。

\(\bm 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. \(zr<i\)。此时我们直接暴力地从第\(i\)位向后匹配求出\(z_{a,i}\)。如果\(z_{a,i}\ne0\)，则令\(zl=i,zr=i+z_{a,i}-1\)；
2. \(zr\ge i\)。设\(i-zl+1=i'\)，即\(i'\)是把跨越\(i\)的z-box\([zl,zr]\)平移至\(a\)的前缀处后\(i\)的位置。此时又分\(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=1递推到i=n
        if(zr<i){//第1种情况
            z[i]=0;
            while(i+z[i]<=s&&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]<=s&&a[i+z[i]]==a[1+z[i]])z[i]++;//后面再暴力匹配
            zl=i;zr=i+z[i]-1;//更新右端点最大的z-box
        }
}

时间复杂度

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

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

z算法的应用

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

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

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

\(\bm2\)道例题

codeforces 526d om nom and necklace

题解传送门

codeforces 427d match & catch

题解传送门