[笔记]（例题更新中）Z函数（扩展KMP）
对于长度为\(n\)的字符串\(S\)，定义\(z[i]\)表示\(S\)本身和\(S[i,n]\)这个后缀的最长公共前缀（LCP）的长度，（特别地，\(z[1]\)可以记为\(0\)或\(n\)）则\(z\)被称为\(S\)的Z函数。
扩展KMP算法可以在\(O(n)\)的时间复杂度内求得\(S\)的Z函数数组。
约定：
- 字符串下标从\(\bf{1}\)开始，下标从\(0\)开始的代码可以参见OI Wiki。
- 本文中\(z[1]=n\)。
正文
定义位置\(i\)的匹配段（也称作Z-box）为区间\([i,i+z[i]-1]\)。
设当前正在处理\(z[i]\)，且\(z[1\sim (i-1)]\)均已经求出。我们设\([l,r]\)表示前\(i-1\)个匹配段中，右端点最大的一个，显然有\(l<i\)。
我们分类讨论\(i\)与\(r\)的位置关系。
- \(i\le r\)：则我们有\(S[i,r]=S[i-l+1,r-l+1]\)，再考虑\((i-l+1)\)的匹配段长度\(z[i-l+1]\)：
- \(z[i-l+1]<(r-i+1)\)：说明\(z[i]=z[i-l+1]\)。
- \(z[i-l+1]\ge(r-i+1)\)：令\(z[i]=r-i+1\)，然后暴力向后匹配直到不能拓展为止。
- \(i>r\)：令\(z[i]=0\)，然后然后暴力向后匹配直到不能拓展为止。
求$z$数组
void getz(int z[],string s,int n){
z[1]=n;
for(int i=2,l=0,r=0;i<=n;i++){
if(i<=r&&z[i-l+1]<r-i+1) z[i]=z[i-l+1];
else{//将1.2和2.合并为一条
z[i]=max(0ll,r-i+1);
while(i+z[i]<=n&&s[z[i]+1]==s[i+z[i]]) z[i]++;
if(i+z[i]-1>r) l=i,r=i+z[i]-1;
}
}
}
时间复杂度的证明和KMP类似，外层for循环执行\(n\)次，内层while循环每执行一次\(r\)都会往右移动\(1\)位，故内层循环总执行次数最多是\(n\)。于是总时间复杂度为\(O(n)\)。
例题
P5410 【模板】扩展 KMP/exKMP（Z 函数）
这道题除了需要求\(B\)的Z函数数组，还需要求\(A\)每个后缀和\(B\)的最长公共前缀，这样就相当于在\(2\)个字符串之间跑Z函数。设我们处理的数组是\(p\)，在\(B\)的Z数组已经求出的前提下，当前处理到\(p[i]\)，和\(p[1\sim(i-1)]\)均已求出。我们设\([l,r]\)表示前\(i-1\)个匹配段中，右端点最大的一个，显然有\(l<i\)。仍然分类讨论\(i\)与\(r\)的位置关系。
- \(i\le r\)：则我们有\(B[i,r]=B[i-l+1,r-l+1]\)，再考虑\((i-l+1)\)的匹配段长度\(z[i-l+1]\)：
- \(z[i-l+1]<(r-i+1)\)：说明\(p[i]=z[i-l+1]\)。
- \(z[i-l+1]\ge(r-i+1)\)：令\(p[i]=r-i+1\)，然后暴力向后匹配直到不能拓展为止。
- \(i>r\)：令\(p[i]=0\)，然后然后暴力向后匹配直到不能拓展为止。
注意循环要从\(1\)开始。
求$p$数组
void ext(int p[],string a,string b,int n){
for(int i=1,l=0,r=0;i<=n;i++){
if(i<=r&&z[i-l+1]<r-i+1) p[i]=z[i-l+1];
else{
p[i]=max(0ll,r-i+1);
while(i+p[i]<=n&&a[i+p[i]]==b[p[i]+1]) p[i]++;
if(i+p[i]-1>r) l=i,r=i+p[i]-1;
}
}
}
全代码
#include<bits/stdc++.h>
#define int long long
#define N 20000010
using namespace std;
string a,b;
int z[N],p[N];
void getz(int z[],string s,int n){
z[1]=n;
for(int i=2,l=0,r=0;i<=n;i++){
if(i<=r&&z[i-l+1]<r-i+1) z[i]=z[i-l+1];
else{
z[i]=max(0ll,r-i+1);
while(i+z[i]<=n&&s[z[i]+1]==s[i+z[i]]) z[i]++;
if(i+z[i]-1>r) l=i,r=i+z[i]-1;
}
}
}
void ext(int p[],string a,string b,int n){
for(int i=1,l=0,r=0;i<=n;i++){
if(i<=r&&z[i-l+1]<r-i+1) p[i]=z[i-l+1];
else{
p[i]=max(0ll,r-i+1);
while(i+p[i]<=n&&a[i+p[i]]==b[p[i]+1]) p[i]++;
if(i+p[i]-1>r) l=i,r=i+p[i]-1;
}
}
}
signed main(){
int n,m;
cin>>a>>b;
n=a.size(),m=b.size(),a=' '+a,b=' '+b;
getz(z,b,m);
ext(p,a,b,n);
int ans=0;
for(int i=1;i<=m;i++) ans^=(i*(z[i]+1));
cout<<ans<<"\n";
ans=0;
for(int i=1;i<=n;i++) ans^=(i*(p[i]+1));
cout<<ans<<"\n";
return 0;
}
\(－ ＴＯ ＢＥ ＣＯＮＴＩＮＵＥＤ －\)