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])当且仅当满足以下全部条件：
- (l e1)；
- (z_{a,l} e0)；
- (r=l+z_{a,l}-1)。
通俗来说，若从(a)的第(i)位开始能与(a)的前缀匹配至少(1)位，那么能匹配的最长的串覆盖过的区间就是一个Z-box。（(l e1)是因为位置(1)很特殊，本身就是前缀，单独考虑）
例如若(a= exttt{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,2sim i-1})和使得(zr)最大的Z-box([zl,zr])，要求出(z_{a,i})并更新(zl,zr)，那么分(2)种情况：
- (zr<i)。此时我们直接暴力地从第(i)位向后匹配求出(z_{a,i})。如果(z_{a,i} e0)，则令(zl=i,zr=i+z_{a,i}-1)；
- (zrge i)。设(i-zl+1=i')，即(i')是把跨越(i)的Z-box([zl,zr])平移至(a)的前缀处后(i)的位置。此时又分(2)种情况：
- (i+z_{a,i'}le zr)。显然(left[i,i+z_{a,i'} ight]subsetneq[zl,zr])。根据Z-box的定义，(forall jinleft[i,i+z_{a,i'} ight],a_j=a_{j-zl+1})。那么从(a)的第(i)位开始与(a)的前缀匹配的情况和从第(i')位开始是一样的，直接令(z_{a,i}=z_{a,i'})，(zl,zr)不变；
- (i+z_{a,i'}>zr)。同理，(forall jin[i,zr],a_j=a_{j-zl+1})。那么(a)的第(isim 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种情况的第2种情况
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_{a,i})时，如果往后暴力匹配（即遇到的不是第(2)种情况的第(1)种情况），那么第(1)次匹配失败就会停下来，所以匹配失败的总次数也为(mathrm{O}(|a|))。因此总时间就是匹配所花的时间(mathrm{O}(|a|)+mathrm{O}(|a|)=mathrm O(|a|))再加上一些赋值、更新(zl,zr)等一些(1)次只要(mathrm O(1))的操作，就还是(mathrm O(|a|))了。得证。
应用
Z算法和ExKMP算法是完全等价的，因为它们求的数组的意思是一样的。但是哈希、KMP能求的东西却有Z算法力所不及的。
Z算法最常用的用法就是字符串模式匹配（这个哈希和KMP也可以做到线性复杂度）。考虑把模式串(b)隔一个不常用字符接到文本串(a)前面，即令(c=b+ exttt{!}+a)。然后求出(z_c)，从(i=|b|+2)到(i=|c|)扫一遍，如果(z_i=|b|)，那么在该位置匹配成功。注意：所谓不常用字符一定不能在串中出现，不然会出bug。如果要用模式串(c)去匹配两个文本串(a,b)，可以令(d=c+ exttt{!}+a+ exttt @+b)，这时两个分隔符不能相同，不然也会出bug。
为什么Z算法在字符串模式匹配上花的时间和哈希相同呢？Z算法算出了从每一位开始能与前缀匹配的最长长度，但是字符串模式匹配只需要知道能否与前缀(c_{1sim|b|})匹配，并未完全使用(z)数组的价值。如果你就是想知道某一位开始能与前缀匹配的最长长度，哈希可就要二分的帮助了，复杂度是带(log)的，不如用Z算法预处理一下。具体的可以参考下面(3)道例题。
不仅如此，Z算法的常数比哈希小（因为为了使哈希不被卡、不在CodeForces上FST，一般要写双重哈希），正确率也比哈希高（Z算法正确率当然是(100\%)啦）。