社区讨论

exKmp 函数完全没有用吧

P5410【模板】扩展 KMP / exKMP(Z 函数)参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@locpx01s
此快照首次捕获于
2023/10/30 17:49
2 年前
此快照最后确认于
2023/11/05 04:38
2 年前
查看原帖
rt,我只需要把 b 串在前 a 串在后拼到一块求个 Z 函数就行了,代码长度减少一半,常数几乎不变。
CPP

#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;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...