蒟蒻刚学OI,Z函数T飞求助
查看原帖
蒟蒻刚学OI,Z函数T飞求助
581316
small_john楼主2023/9/25 13:02
#include <bits/stdc++.h>
#define re register
using namespace std;
const int N = 4e7+5;
string a,b;
int z[N];
long long ans1,ans2;
inline void Z(string s)
{
	int n = s.size();
	s = ' '+s;
	for(re int i = 2,l = 0;i<=n;i++)
	{
		if(l+z[l+1]>i) z[i] = min(z[i-l+1],l+z[l+1]-i); 
		else while(i+z[i]<=n&&s[z[i]+1]==s[z[i]+i])
			z[i]++;
		if(l+z[l+1]<i+z[i]) l = i;
	}
}
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	Z(b+a);
	ans1 = b.size()+1;
	for(re int i = 2;i<=b.size();i++) ans1^=1ll*(min(z[i],(int)b.size()-i+1)+1)*i;
	for(re int i = 1;i<=a.size();i++) ans2^=1ll*(min(z[i+(int)b.size()],(int)b.size())+1)*i;
	cout<<ans1<<'\n'<<ans2;
	return 0;
}

记录

2023/9/25 13:02
加载中...