需要维护 [l,r]，r=\max\limits_{j=1}^{i-1} j+z(j)-1，l 为 r 的取值对应的 j。
每次要么 $O(1)$ 转移，要么 $r$ 至少 $+1$，复杂度 $O(n)$。
```cpp
#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;
}
```