萌新求助 TLE79pts 的 exkmp
查看原帖
萌新求助 TLE79pts 的 exkmp
350270
CatFromMars楼主2024/8/8 14:12

如题,刚学 exkmp,理解应该有不太对的地方,感觉是哪里写假了,但是不太清楚,请各位巨佬帮忙指正,谢谢 qwq

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e7;
int z[N + 10];
string s1, s2, str = "#";
void getz() {
	int n = str.size() - 1;
	int ml = 1;
	z[1] = 0;
	for(int i = 2; i <= n; i++) {
		if(i <= ml + z[ml] - 1) z[i] = min(ml + z[ml] - i, z[i - ml + 1]);
		while(z[i] <= n && str[i + z[i]] == str[z[i] + 1]) z[i]++;
		if(i + z[i] - 1 > ml + z[i] - 1) ml = i;
	}
	z[1] = s2.size();
	ll sum1 = 0, sum2 = 0;
	for(int i = 1; i <= s2.size(); i++)
		sum1 ^= (ll)((ll)(i) * (ll)(z[i] + 1));
	for(int i = s2.size() + 2; i <= n; i++)
		sum2 ^= (ll)((ll)(i - s2.size() - 1) * (ll)(z[i] + 1));
	cout << sum1 << "\n" << sum2;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> s1 >> s2;
	str += s2, str += "#", str += s1;
	getz();
}
2024/8/8 14:12
加载中...