天天看点
返回

Z-Algorithm详解Z-Algorithm详解

Z-Algorithm详解

0.前言

给你一个文本串 t t t和一个模式串 p p p，让你寻找 p p p在 t t t中出现的所以位置。

例如， t = " a b a c a b a b a c " t="abacababac" t="abacababac"， p = " a b a " p="aba" p="aba"，那么 p p p在 t t t中出现了 3 3 3次，起始位置在 t t t中的下标分别是 1 1 1， 5 5 5， 7 7 7。

很显然可以想到 O ( ∣ t ∣ ∗ ∣ p ∣ ) O(|t|*|p|) O(∣t∣∗∣p∣)的暴力算法，即以每一个位置为起始位置，暴力匹配每一个字符。但是如果 t t t和 p p p的长度都是 1 0 5 10^5 105级别的就会超时，我们需要更高效的方法。在中国有一个 K M P KMP KMP算法比较流行，但是我个人比较喜欢 Z − a l g o r i t h m Z-algorithm Z−algorithm。这里我给大家讲一下这个。

1.一些函数的定义

我们定义 z i ( s ) z_i(s) zi​(s)为对于所有的 2 ≤ i ≤ ∣ s ∣ 2 \leq i \leq |s| 2≤i≤∣s∣，以 i i i开头的子串和 s s s的最长公共前缀的长度

如：

s = " a b a " s="aba" s="aba"，那么 z 3 ( s ) = 1 z_3(s)=1 z3​(s)=1（以 3 3 3为起始位置，能够匹配 s s s长度为 1 1 1的前缀 " a " "a" "a"，但匹配不了长度为 2 2 2的前缀 " a b " "ab" "ab")。

s = " a b c a b c a b " s="abcabcab" s="abcabcab"，那么 z 4 ( s ) = 5 z_4(s)=5 z4​(s)=5

s = " a b a c a b a b a c a " s="abacababaca" s="abacababaca"，那么 z 5 ( s ) = 3 , z 7 ( s ) = 5 z_5(s)=3, z_7(s)=5 z5​(s)=3,z7​(s)=5

2.如果已知 z i z_i zi​的值如何求出答案

我们将 p p p粘在 s s s的前面，中间用一个字符（如下划线）隔开，可以得到一个字符串 s s s。我们假设我们已经知道了所有 z i ( s ) z_i(s) zi​(s)的值，那么怎么求出答案呢。

我们可以扫描 s s s串中从 ∣ p ∣ + 2 |p|+2 ∣p∣+2一直到 ∣ p ∣ + ∣ t ∣ + 1 |p|+|t|+1 ∣p∣+∣t∣+1的位置 i i i，也就是原来的 t t t字符串的位置，然后判断 z i ( s ) z_i(s) zi​(s)是否等于 p p p字符串的长度。如果等于，那么在以 t t t字符串的这个位置就可以匹配 p p p字符串。

为什么这个方法是正确的？

首先，根据 z i ( s ) z_i(s) zi​(s)的定义，它表示以 i i i开头的子串和 s s s的最长公共前缀的长度。我们知道， s s s是由 p p p粘在 t t t的前面得到的，因此 s s s的前缀实际上就是 p p p字符串，而又因为我们 p p p和 t t t之间用一个字符隔开，所有 z i ( s ) z_i(s) zi​(s)的值永远不可能大于 ∣ p ∣ |p| ∣p∣。这样我们就知道如果 z i ( s ) = ∣ p ∣ z_i(s)=|p| zi​(s)=∣p∣就表示匹配成功。

3.怎样求出 z i z_i zi​

我们首先定义一个 b o x i box_i boxi​为区间 [ i , i + z i − 1 ] [i,i+z_i-1] [i,i+zi​−1]。我们假设当前我们在计算 z i ( s ) z_i(s) zi​(s)的值，那么我们定义 [ l , r ] [l,r] [l,r]为 b o x 2 , b o x 3 , … , b o x i − 1 box_2,box_3,\dots,box_{i-1} box2​,box3​,…,boxi−1​中最靠右的 b o x box box的左右端点。

那么有以下几种情况：

1.若 i > r i \gt r i>r，则证明前面的所有的 b o x j box_j boxj​和我们没有任何关联，我们无法利用，同时也证明 b o x i box_i boxi​一定是最靠右的，更新 l = i l=i l=i， r = i + z i − 1 r=i+z_i-1 r=i+zi​−1，暴力匹配就行了。

2.若 i ≤ r i \leq r i≤r，则令 i ′ = i − l + 1 i'=i-l+1 i′=i−l+1，因为 i i i位于 [ l , r ] [l,r] [l,r]内，则我们知道 s l , s l + 1 , … , s r s_l,s_{l+1},\dots,s_r sl​,sl+1​,…,sr​应该与 s 1 , s 2 , … , s r s_1,s_2,\dots,s_r s1​,s2​,…,sr​匹配。因此我们可以将 [ l , r ] [l,r] [l,r]平移到 [ 1 , r − l + 1 ] [1,r-l+1] [1,r−l+1]上去， i ′ i' i′其实就是 i i i在这段区间中的对应位置。因此我们可以根据 z i ′ ( s ) z_{i'}(s) zi′​(s)的数值来计算 z i ( s ) z_i(s) zi​(s)，我们令 β = r − i + 1 \beta=r-i+1 β=r−i+1。

下面我们又可以分出两种情况：

( 1 ) (1) (1) z i ′ ( s ) &lt; β z_{i&#x27;}(s)&lt;\beta zi′​(s)<β。即 b o x i ′ box_{i&#x27;} boxi′​这个位置控制的右端点并没有超过 r r r，直接令 z i = z i ′ z_i=z_{i&#x27;} zi​=zi′​， l , r l,r l,r保持原样。

( 2 ) (2) (2) z i ′ ( s ) ≥ β z_{i&#x27;}(s)\geq\beta zi′​(s)≥β。 b o x i ′ box_{i&#x27;} boxi′​的右端点超过了超过了 [ l , r ] [l,r] [l,r]对应的前缀。因为我们仅仅知道 s l , s l + 1 , … , s r s_l,s_{l+1},\dots,s_r sl​,sl+1​,…,sr​与 s 1 , s 2 , … , s r s_1,s_2,\dots,s_r s1​,s2​,…,sr​匹配，还不知道后面的部分。因此我们更新 l = i l=i l=i，继续暴力匹配后面的长度，匹配完成后更新 z i = r − l z_i=r-l zi​=r−l。

4.时间复杂度

我们发现 r r r是单调递增的，因此时间复杂度也是线性的。（类似于 t w o   p o i n t e r s two\ pointers two pointers)。

5.完整代码

Z − A l g o r i t h m Z-Algorithm 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.例题

C o d e f o r c e s   126 B − P a s s w o r d Codeforces\ 126B - Password Codeforces 126B−Password

思路：扫一遍，判断是否合法即可。 Z − a l g o r i t h m Z-algorithm Z−algorithm的基础题，建议没接触过 Z − a l g o r i t h m 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]);
}

C o d e f o r c e s   427 D − M a t c h &amp; C a t c h Codeforces\ 427D - Match\&amp;Catch Codeforces 427D−Match&Catch

思路：将 s s s的每个后缀接在 s s s的前面，用一个字符隔开。再将得到的字符串接在 t t t的前面，用一个字符隔开，对这个字符串进行 Z − a l g o r i t h m Z-algorithm Z−algorithm，求出 z i z_i 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;
}

C o d e f o r c e s   526 D − O m N o m a n d N e c k l a c e Codeforces\ 526D - Om Nom and Necklace Codeforces 526D−OmNomandNecklace

思路：对整个字符串进行一次 Z − a l g o r i t h m Z-algorithm Z−algorithm，然后枚举 A − B A-B 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');
	}
}

C o d e f o r c e s   1200 E − C o m p r e s s W o r d s Codeforces\ 1200E - Compress Words Codeforces 1200E−CompressWords

话说这是 6 6 6天前刚比完的一场 D i v . 2 Div.2 Div.2的 E E E

思路：对于每一个字符串，以它作为模式串 p p p，并取当前答案的后 m i n ( a n s . s i z e ( ) , s [ i ] . s i z e ( ) ) min(ans.size(),s[i].size()) min(ans.size(),s[i].size())位所为文本串 t t t，进行 Z − a l g o r i t h m Z-algorithm Z−algorithm，最后判断一下是否有位置 i i i使得 i + z i = t . s i z e ( ) i+z_i=t.size() 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 − a l g o r i t h m Z-algorithm Z−algorithm的更多练习题，大家有时间尽量做哦：

CF119D String Transformation
CF631D Messenger
CF535D Tavas and Malekas
CF955D Scissors
CF149E Martian Strings
算法 字符串 codeforces Z-algorithm z
上一篇: 窗体间动态传值
下一篇: Vue框架学习笔记 每天学习----五

继续阅读