exKMP模板全wa求条
查看原帖
exKMP模板全wa求条
947029
Chen_Three楼主2025/2/8 13:05
#include<bits/stdc++.h>
using namespace std;
const int N = 2e7 + 5;
int z[N], ex[N];
int main(){
	string a, b;
	cin >> a >> b;
	a = " " + a, b = " " + b;
	z[1] = b.size() - 1;
	for(int i = 2, l = 0, r = 0; i < b.size(); i++){
		if(i <= r && z[i - l + 1] < r - i + 1) z[i] = z[i - l + 1];
		else{
			z[i] = max(0, r - i + 1);
			while(i + z[i] < b.size() && b[z[i] + 1] == b[i + z[i]]) z[i]++;
		}
		if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
	}
	//for(int i = 1; i < b.size(); i++) cout << z[i] << " ";
	for(int i = 1, l = 0, r = 0; i < a.size(); i++){
		if(i <= r && z[i - l + 1] < r - i + 1) ex[i] = z[i - l + 1];
		else{
			ex[i] = max(0, r - i + 1);
			while(i + ex[i] < a.size() && b[ex[i] + 1] == a[i + ex[i]]) ex[i]++;
		}
		if(i + ex[i] - 1 > r) l = i, r = i + ex[i] - 1;
	}
	//for(int i = 1; i < a.size(); i++) cout << ex[i] << " ";
	int ans1 = 0, ans2 = 0;
	for(int i = 1; i < b.size(); i++) ans1 ^= i * (z[i] + 1);
	for(int i = 1; i < a.size(); i++) ans2 ^= i * (ex[i] + 1);
	cout << ans1 << "\n" << ans2;
	return 0;
}
2025/2/8 13:05
加载中...