社区讨论
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 条回复,欢迎继续交流。
正在加载回复...