0分,求指点
查看原帖
0分,求指点
660776
ananran998楼主2023/4/30 16:05
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char s[10000002], p[20000002];
int m, n, z[20000001];

inline void kmp() {
	m = strlen(p + 1), n = strlen(s + 1);
	p[m + 1] = '#';
	for (int i = 1, j = m + 2; i <= n; i++, j++)
		p[j] = s[i];
	int M = 1, R = 0;
	z[1] = 0;
	for (int i = 2; i <= n + m + 1; i++) {
		if (i > R)
			z[i] = 0;
		else
			z[i] = min(i - M + 1, R - i + 1);
		while (i + z[i] <= n + m + 1 && p[i + z[i]] == p[z[i] + 1])
			++z[i];
		if (i + z[i] - 1 > R)
			M = i, R = i + z[i] - 1;
	}
	z[1] = m;
	ll ans = 0;
	for (int i = 1; i <= m; i++)
		ans ^= 1LL * (i * (z[i] + 1));
	printf("%lld\n", ans);
	ans = 0;
	for (int i = m + 2; i <= n + m + 1; i++)
		ans ^= 1LL * (i - m - 1) * (z[i] + 1);
	printf("%lld\n", ans);
}

int main() {
	scanf("%s%s", s + 1, p + 1);
	kmp();
	return 0;
}
2023/4/30 16:05
加载中...