题解：P5410 【模板】扩展 KMP/exKMP（Z 函数）

· · 题解

关于KMP

原题地址

当看完这个视频，你可能就懂什么是KMP了,那么，上代码！！！

#include <bits/stdc++.h>
#define int long long
using namespace std;
char a[20000010], b[20000010];
int z[20000010], p[20000010], ans1, ans2;
int n, m;
signed main() {
    scanf("%s%s", a, b);
    n = strlen(a);
    m = strlen(b);
    z[0] = m;
    for (int i = 1, l = 0, r = 0; i < m; i ++) {
        if (i <= r) z[i] = min(z[i - l], r - i + 1);
        while (i + z[i] < m && b[z[i]] == b[i + z[i]]) z[i] ++;
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    for (int i = 0, l = 0, r = 0; i < n; i ++) {
        if (i <= r&&i)
            p[i] = min(z[i - l], r - i + 1);
        while (p[i] < m && i + p[i] < n && b[p[i]] == a[i + p[i]])
            p[i] ++;
        if (i + p[i] - 1 > r)
            l = i,
            r = i + p[i] - 1;
    }
    for (int i = 0; i < m; i ++)
        ans1 ^= 1ll * (i + 1) * (z[i] + 1);
    for (int i = 0; i < n; i ++)
        ans2 ^= 1ll * (i + 1) * (p[i] + 1);
    printf("%lld\n%lld\n", ans1, ans2);
    return 0;
}