Z-Algorithm详解
0.前言
给你一个文本串t和一个模式串p，让你寻找p在t中出现的所以位置。
例如，t="abacababac"，p="aba"，那么p在t中出现了3次，起始位置在t中的下标分别是1，5，7。
很显然可以想到O(∣t∣∗∣p∣)的暴力算法，即以每一个位置为起始位置，暴力匹配每一个字符。但是如果t和p的长度都是105级别的就会超时，我们需要更高效的方法。在中国有一个KMP算法比较流行，但是我个人比较喜欢Z−algorithm。这里我给大家讲一下这个。
1.一些函数的定义
我们定义zi(s)为对于所有的2≤i≤∣s∣，以i开头的子串和s的最长公共前缀的长度
如：
s="aba"，那么z3(s)=1（以3为起始位置，能够匹配s长度为1的前缀"a"，但匹配不了长度为2的前缀"ab")。
s="abcabcab"，那么z4(s)=5
s="abacababaca"，那么z5(s)=3,z7(s)=5
2.如果已知zi的值如何求出答案
我们将p粘在s的前面，中间用一个字符（如下划线）隔开，可以得到一个字符串s。我们假设我们已经知道了所有zi(s)的值，那么怎么求出答案呢。
我们可以扫描s串中从∣p∣+2一直到∣p∣+∣t∣+1的位置i，也就是原来的t字符串的位置，然后判断zi(s)是否等于p字符串的长度。如果等于，那么在以t字符串的这个位置就可以匹配p字符串。
为什么这个方法是正确的？
首先，根据zi(s)的定义，它表示以i开头的子串和s的最长公共前缀的长度。我们知道，s是由p粘在t的前面得到的，因此s的前缀实际上就是p字符串，而又因为我们p和t之间用一个字符隔开，所有zi(s)的值永远不可能大于∣p∣。这样我们就知道如果zi(s)=∣p∣就表示匹配成功。
3.怎样求出zi
我们首先定义一个boxi为区间[i,i+zi−1]。我们假设当前我们在计算zi(s)的值，那么我们定义[l,r]为box2,box3,…,boxi−1中最靠右的box的左右端点。
那么有以下几种情况：
1.若i>r，则证明前面的所有的boxj和我们没有任何关联，我们无法利用，同时也证明boxi一定是最靠右的，更新l=i，r=i+zi−1，暴力匹配就行了。
2.若i≤r，则令i′=i−l+1，因为i位于[l,r]内，则我们知道sl,sl+1,…,sr应该与s1,s2,…,sr匹配。因此我们可以将[l,r]平移到[1,r−l+1]上去，i′其实就是i在这段区间中的对应位置。因此我们可以根据zi′(s)的数值来计算zi(s)，我们令β=r−i+1。
下面我们又可以分出两种情况：
(1) zi′(s)<β。即boxi′这个位置控制的右端点并没有超过r，直接令zi=zi′，l,r保持原样。
(2) zi′(s)≥β。boxi′的右端点超过了超过了[l,r]对应的前缀。因为我们仅仅知道sl,sl+1,…,sr与s1,s2,…,sr匹配，还不知道后面的部分。因此我们更新l=i，继续暴力匹配后面的长度，匹配完成后更新zi=r−l。
4.时间复杂度
我们发现r是单调递增的，因此时间复杂度也是线性的。（类似于two pointers)。
5.完整代码
Z−Algorithm的完整代码：
#include <bits/stdc++.h>
using namespace std;
int n,z[200005];
char t[100005],p[100005],x[200005];
inline void Z_algorithm(){
memset(z,0,sizeof(z));
int l=0,r=0;
for(int i=1;i<n;i++){
if(i<=r) z[i]=min(z[i-l],r-i);
while(i+z[i]<n&&x[z[i]]==x[i+z[i]]) z[i]++;
if(i+z[i]>r){
l=i;
r=i+z[i];
}
}
}
int main(){
scanf("%s%s",t+1,p+1);
for(int i=1;i<=strlen(p+1);i++) x[n++]=p[i];
x[n++]='_';
for(int i=1;i<=strlen(t+1);i++) x[n++]=t[i];
Z_algorithm();
vector<int> ans;
for(int i=strlen(p+1)+1;i<n;i++)
if(z[i]==strlen(p+1))
ans.push_back(i-strlen(p+1));
for(int i=0;i<ans.size();i++) printf("%d ",ans[i]);
}
6.例题
Codeforces 126B−Password
思路：扫一遍，判断是否合法即可。Z−algorithm的基础题，建议没接触过Z−algorithm的先做这道题。
#include <bits/stdc++.h>
using namespace std;
char s[1000005];
int n,z[1000005];
inline void Z_algorithm(){
int l=0,r=0;
for(int i=1;i<n;i++){
if(i<=r) z[i]=min(z[i-l],r-i);
while(i+z[i]<n&&s[i+z[i]]==s[z[i]]) z[i]++;
if(i+z[i]>r){
l=i;
r=i+z[i];
}
}
}
int main(){
scanf("%s",s);
n=strlen(s);
Z_algorithm();
int maxx=0,pos=0;
for(int i=1;i<n;i++){
if(z[i]==n-i&&maxx>=n-i){
pos=i;
break;
}
maxx=max(maxx,z[i]);
}
if(!pos) puts("Just a legend");
else
for(int i=0;i<n-pos;i++)
putchar(s[i]);
}
Codeforces 427D−Match&Catch
思路：将s的每个后缀接在s的前面，用一个字符隔开。再将得到的字符串接在t的前面，用一个字符隔开，对这个字符串进行Z−algorithm，求出zi中最大值和次大值，判断一下就行了。
#include <bits/stdc++.h>
using namespace std;
int n,m,tot;
char s[5005],t[5005],x[15005];
int z[15005],ans=INT_MAX;
inline void Z_algorithm(){
memset(z,0,sizeof(z));
int l=0,r=0;
for(int i=1;i<tot;i++){
if(i<=r) z[i]=min(z[i-l],r-i);
while(i+z[i]<tot&&x[z[i]]==x[i+z[i]]) z[i]++;
if(i+z[i]>r){
l=i;
r=i+z[i];
}
}
}
int main(){
scanf("%s%s",s+1,t+1);
n=strlen(s+1),m=strlen(t+1);
for(int i=1;i<=n;i++){
memset(x,0,sizeof(x));tot=0;
for(int j=i;j<=n;j++) x[tot++]=s[j];
x[tot++]='$';
for(int j=1;j<=n;j++) x[tot++]=s[j];
x[tot++]='#';
for(int j=1;j<=m;j++) x[tot++]=t[j];
Z_algorithm();
z[n+1]=0;
int f=0,g=0,idx=-1;
bool good=false;
for(int j=1;j<tot;j++){
if(z[j]>f){
g=f;
f=z[j];
idx=j;
good=1;
}
else if(z[j]==f) good=0;
else if(z[j]>g) g=z[j];
}
if(good&&idx>2*n-i+1) ans=min(ans,g+1);
}
if(ans==INT_MAX) puts("-1");
else cout<<ans<<endl;
}
Codeforces 526D−OmNomandNecklace
思路：对整个字符串进行一次Z−algorithm，然后枚举A−B段的长度，判断一下即可。
#include <bits/stdc++.h>
using namespace std;
int n,k,a[1000005],z[1000005],sum=0;
char x[1000005];
inline void Z_algorithm(){
memset(z,0,sizeof(z));
int l=0,r=0;
for(int i=1;i<n;i++){
if(i<=r) z[i]=min(z[i-l],r-i);
while(i+z[i]<n&&x[z[i]]==x[i+z[i]]) z[i]++;
if(i+z[i]>r){
l=i;
r=i+z[i];
}
}
}
int main(){
scanf("%d%d%s",&n,&k,x);
Z_algorithm();
for(int len=1;len*k<=n;len++){
if(z[len]>=len*(k-1)){
a[len*k]++;
a[min(len*k+len,len+z[len])+1]--;
}
}
for(int i=1;i<=n;i++){
sum+=a[i];
if(sum>0) putchar('1');
else putchar('0');
}
}
Codeforces 1200E−CompressWords
话说这是6天前刚比完的一场Div.2的E
思路：对于每一个字符串，以它作为模式串p，并取当前答案的后min(ans.size(),s[i].size())位所为文本串t，进行Z−algorithm，最后判断一下是否有位置i使得i+zi=t.size()即可。
#include <bits/stdc++.h>
using namespace std;
int n,z[1000005];
string s[100005],ans,x;
inline void Z_algorithm(){
int l=0,r=0;
for(int i=1;i<x.size();i++){
z[i]=0;
if(i<=r) z[i]=min(z[i-l],r-i);
while(i+z[i]<x.size()&&x[i+z[i]]==x[z[i]]) z[i]++;
if(i+z[i]>r){
l=i;
r=i+z[i];
}
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
cin>>s[i];
x=s[i]+"_"+ans.substr(ans.size()-min(ans.size(),s[i].size()));
Z_algorithm();
int maxx=0;
for(int j=s[i].size()+1;j<x.size();j++)
if(z[j]==x.size()-j)
maxx=max(maxx,z[j]);
ans+=s[i].substr(maxx);
}
for(int i=0;i<ans.size();i++) putchar(ans[i]);
}
7.更多练习题
Z−algorithm的更多练习题，大家有时间尽量做哦：
CF119D String Transformation
CF631D Messenger
CF535D Tavas and Malekas
CF955D Scissors
CF149E Martian Strings