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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using UI = unsigned int;
using ULL = unsigned long long;
using DB = double;
using LDB = long double;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
#define CP(x) complex<x>
#define fst first
#define snd second
#define popcnt(i) __builtin_popcount(i)

const int N = 2e7 + 5;

int n, m;
string a, b;
int z[N], ext[N];

void exKMP() {
    int l = 0, r = 0;
    z[1] = m;
    for (int i = 2; i <= m; i++) {
        if (i > r) {
            z[i] = 0;
            while (i + z[i] <= m && b[z[i] + 1] == b[i + z[i]]) {
                ++z[i];
            }
            l = i, r = i + z[i] - 1;
        } else if (z[i - l + 1] < r - i + 1) {
            z[i] = z[i - l + 1];
        } else {
            z[i] = r - i + 1;
            while (i + z[i] <= m && b[z[i] + 1] == b[i + z[i]]) {
                ++z[i];
            }
            l = i, r = i + z[i] - 1;
        }
    }
    l = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        if (i > r) {
            ext[i] = 0;
            while (ext[i] < m && i + ext[i] <= n && b[ext[i] + 1] == a[i + ext[i]]) {
                ++ext[i];
            }
            l = i, r = i + ext[i] - 1;
        } else if (z[i - l + 1] < r - i + 1) {
            ext[i] = z[i - l + 1];
        } else {
            ext[i] = r - i + 1;
            while (ext[i] < m && i + ext[i] <= n && b[ext[i] + 1] == a[i + ext[i]]) {
                ++ext[i];
            }
            l = i, r = i + ext[i] - 1;
        }
    }
}

void solve() {
    cin >> a >> b;
    n = a.size(), m = b.size();
    a = ' ' + a, b = ' ' + b;
    
    exKMP();

    LL ans1 = 0, ans2 = 0;
    for (int i = 1; i <= m; i++) ans1 ^= (LL)i * (z[i] + 1);
    for (int i = 1; i <= n; i++) ans2 ^= (LL)i * (ext[i] + 1);
    cout << ans1 << '\n' << ans2 << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}