题目传送门

思路

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

暴力计算 zz 函数是 O(n2)O(n^2) 的,考虑将计算的 zz 函数用起来。

我们顺次计算 zz 函数,假设现在需要计算第 ziz_i,记区间 [l,r][l,r] 为满足 1i<i1 \le i < is[l:r]=s[1:rl+1]s[l : r] = s[1 : r-l+1] 的使得 rr 最大的区间,初始时 l=r=0l=r=0

iri \le r 时,根据定义显然有 s[i:r]=s[il:rl]s[i:r]=s[i-l:r-l],那么可以将 ziz_i 预处理为 min(zil,ri+1)\min(z_{i-l},r-i+1) ,然后进行暴力;

i>ri > r 时,直接进行暴力。

zz 函数的过程

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

两串匹配类似。

代码

#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;
}