求助15tps,只A#2#13
查看原帖
求助15tps,只A#2#13
672334
szlh_Carey005楼主2025/7/24 22:08

rt

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e7+10;
string a, b;
ll ans1, ans2, z[N], ext[N];
void get_z(string str)
{
	int len = str.size();
	int p = 0, k = 1, l, j;
	z[0] = len;
	while(p+1 < len && str[p] == str[p+1]) p++;
	z[1] = p;
	for(int i = 2; i < len; ++i)
	{
		p = k + z[k] - 1;
		l = z[i-k];
		if(p <= i + l)
		{
			j = max(0, p - i + 1);
			while(i+j < len && str[i+j] == str[j]) j++;
			z[i] = j;
			k = i;
		}
		else z[i] = l;
	}
}
void exkmp(string s1, string s2)
{
	int n = s1.size(), m = s2.size(), p = 0, k = 0, l, j;
	while(p < n && p < m && s1[p] == s2[p]) p++;
	ext[0] = p;
	for(int i = 1; i < n; ++i)
	{
		p = k + ext[k] - i;
		l = z[i-k];
		if(p <= i + l)
		{
			j = max(0, p);
			while(i+j < n && j < m && s1[i+j] == s2[j]) j++;
			ext[i] = j;
			k = i;
		}
		else ext[i] = l;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> a >> b;
	get_z(b);
	exkmp(a, b);
	for(int i = 0; i < (int)b.size(); ++i) ans1 ^= (i+1) * (z[i]+1);
	for(int i = 0; i < (int)a.size(); ++i) ans2 ^= (i+1) * (ext[i]+1);
	cout << ans1 << '\n' << ans2;
	return 0;
}
2025/7/24 22:08
加载中...