exKmp 函数完全没有用吧
查看原帖
exKmp 函数完全没有用吧
122144
hs_black楼主2021/1/20 08:35

rt,我只需要把 b 串在前 a 串在后拼到一块求个 Z 函数就行了,代码长度减少一半,常数几乎不变。


#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20000009;
char s[N<<1], t[N];
int z[N<<1], m, n;
void Z(char *s, int n) {
	z[1] = n;
	for (int i = 2, l = 0, r = 0;i <= n; ++i) {
		if (i <= r) z[i] = min(z[i - l + 1], r - i + 1);
		while (i + z[i] <= n && s[i + z[i]] == s[z[i] + 1]) ++z[i];
		if (i + z[i] - 1 >= r) l = i, r = i + z[i] - 1;
	}
}

int main() {
	scanf ("%s%s", t + 1, s + 1);
	n = strlen(s + 1), m = strlen(t + 1);
	for (register int i = 1;i <= m; ++i) s[i + n] = t[i];
	Z(s, n + m);
	unsigned long long ans1 = 0, ans2 = 0;
	for (register int i = 1;i <= n; ++i) ans1  ^= 1ull * i * (min(z[i], n - i + 1) + 1);
	for (register int i = 1;i <= m; ++i) ans2  ^= 1ull * i * (min(n, z[i + n]) + 1);
	printf ("%llu\n%llu", ans1, ans2);
	return 0;
}

2021/1/20 08:35
加载中...