一些約定：

• 字符串下標從 \(1\) 開始。
• \(s[1,i]\) 表示字符串 \(s\) 的第一個到第 \(i\) 個字符組成的字符串。

Z 函數

我們定義：

• \(z[i]\) 表示最大的 \(len\) 使得 \(B[1,len]=B[i,i+len-1]\)。其中 \(z[1]=m\)。

• \(Z-box\)：這是我們在求 \(z\) 數組時維護的一段區間，用兩個變量 \(l,r\) 表示，它表示目前為止 \(B\) 中右端點最大的一個區間 \([l,r]\) 滿足，\(B[l,r]=B[1,r-l+1]\)。

知道了一些定義我們就來看 \(z\) 數組怎么求。
假設我們已經得出 \(z[1]~z[i-1]\) 了要求 \(z[i]\)，且目前的 \(Z-box=[l,r]\)。

1. \(l \le i \le r\) (實際上如果 \(i \le r\) , \(i\) 一定滿足 \(l \le i \le r\))：

設 \(r’\) 表示 \(r-l+1\)，則 \(B[1,r’]=B[l,r]\) (為了下面敘述方便，我們稱 \(r’\) 為 \(r\) 的對應點)，圖片中相同顏色代表這段區間相同。

我們再求出 \(i\) 的對應點 \(i’=i-l+1\)，則 \(B[i’,r’]=B[i,r]\)。

假設 \(z[i’]=len\) 則 \(B[1,len]=B[i’,i’+len-1]\)，現在又有兩種情況：

• \(len \le r-i+1\)： 此時 \(B[1,len]=B[i’,i’+len-1]=B[i,i+len-1]\)，又因為 \(i+len-1\) 并未超過 \(Z-box\) 的右端點，所以必有 \(z[i]=len\)。

  

• 而如果 \(len>r-i+1\)，如下圖

  

我們無法確定綠色部分是否相同，因此不能直接把 \(len\) 賦給 \(z[i]\)，但我們可以保證 \(z[i]\ge r-i+1\)，\(r\) 后面的部分我們暴力掃描判斷。

2. \(i>r\)： 同樣也是暴力往后掃描即可。

每次求完 \(z[i]\) 后如果 \(i+z[i]-1>r\) 則用 \(i\) 和 \(i+z[i]-1\) 更新 \(l,r\)。

求 \(z\) 數組的代碼如下：

	z[1]=m,l=0,r=0;
	for(int i=2;i<=m;i++)
	{
		if(i<=r) z[i]=min(z[i-l+1],r-i+1);
		while(b[i+z[i]]==b[1+z[i]]) z[i]++; //如果i>r那這里z[i]一開始是0
		if(i+z[i]-1>r) r=i+z[i]-1,l=i; 
	}

復雜度分析： 會發現一旦出現暴力遍歷的情況必然會更新右端點 \(r\)，而右端點只能更新 \(O(n)\) 次，再 \(r=n\) 之后就不會出現暴力掃描的情況了，因此復雜度是 \(O(n)\)。

P5410 【模板】擴展 KMP/exKMP（Z 函數）

求解 \(p\) 數組的過程是差不多的。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e7+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
char a[N],b[N];
int n,m;
string s1,s2;
int z[N],p[N];
int l,r;
int ans1,ans2;
signed main()
{
	cin>>s1>>s2;
	n=s1.size(),m=s2.size();
	for(int i=1;i<=n;i++) a[i]=s1[i-1];
	for(int i=1;i<=m;i++) b[i]=s2[i-1];
	z[1]=m,l=0,r=0;
	for(int i=2;i<=m;i++){
		if(i<=r) z[i]=min(z[i-l+1],r-i+1);
		while(b[i+z[i]]==b[1+z[i]]) z[i]++;
		if(i+z[i]-1>r) r=i+z[i]-1,l=i; 
	}
	for(int i=1;i<=m;i++){
		ans1^=(z[i]+1)*i;
	}
	l=0,r=0;
	for(int i=1;i<=n;i++){
		if(i<=r) p[i]=min(z[i-l+1],r-i+1);
		while(a[i+p[i]]==b[1+p[i]]&&i+p[i]<=n&&1+p[i]<=m) p[i]++;   
			//注意這里要判斷邊界 
		if(i+p[i]-1>r) r=i+p[i]-1,l=i;
	}
	for(int i=1;i<=n;i++){
		ans2^=(p[i]+1)*i;
	}
	printf("%lld\n%lld\n",ans1,ans2);
	return 0;
}

本博客參考的網址：

[C++]洛谷：【模板】擴展 KMP（Z 函數） 算法詳解