【模板】扩展 KMP（Z 函数）

题目传送门

思路

对于一个字符串 $s$，$z_i := |\operatorname{LCP}(s,s[i:])|$，即 $s$ 从 $i$ 开始的后缀与 $s$ 的最大匹配。

暴力计算 $z$ 函数是 $O(n^2)$ 的，考虑将计算的 $z$ 函数用起来。

我们顺次计算 $z$ 函数，假设现在需要计算第 $z_i$，记区间 $[l,r]$ 为满足 $1 \le i < i$ 且 $s[l : r] = s[1 : r-l+1]$ 的使得 $r$ 最大的区间，初始时 $l=r=0$。

当 $i \le r$ 时，根据定义显然有 $s[i:r]=s[i-l:r-l]$，那么可以将 $z_i$ 预处理为 $\min(z_{i-l},r-i+1)$ ，然后进行暴力；

当 $i > r$ 时，直接进行暴力。

看 $z$ 函数的过程

时间复杂度显然是线性的。

两串匹配类似。

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e7 + 10;

int N , M , Z[MAXN] , P[MAXN];
string S1 , S2;

void Get_Z(string s , int N) {
	Z[1] = N;
	for(int i = 2 , l = 0 , r = 0; i <= N; i++) {
		if(i <= r) Z[i] = min(Z[i - l + 1] , r - i + 1);
		while(i + Z[i] <= N && s[i + Z[i]] == s[Z[i] + 1]) ++Z[i];
		if(i + Z[i] - 1 > r) l = i , r = i + Z[i] - 1;
	}
}

void ExKMP(string s , int N , string t , int M) {
	Get_Z(t , M);
	for(int i = 1 , l = 0 , r = 0; i <= N; i++) {
		if(i <= r) P[i] = min(Z[i - l + 1] , r - i + 1);
		while(i + P[i] <= N && s[i + P[i]] == t[P[i] + 1]) ++P[i];
		if(i + P[i] - 1 > r) l = i , r = i + P[i] - 1;
	}
}

int main() {
	cin >> S1 >> S2;
	N = S1.size();
	M = S2.size();
	
	S1 = " " + S1;
	S2 = " " + S2;
	
	ExKMP(S1 , N , S2 , M);
	
	long long Ans = 0;
	
	for(int i = 1; i <= M; i++) Ans ^= 1ll * i * (Z[i] + 1);
	
	cout << Ans << endl;
	
	Ans = 0;
	
	for(int i = 1; i <= N; i++) Ans ^= 1ll * i * (P[i] + 1);
	
	cout << Ans << endl;
	return 0;
}