求出一个字符串 \(s\) 的每个后缀与原串的 LCP。
首先由显然的 SAM 做法。考虑线性。
考虑维护区间 \([l,r]\) 表示 \([l,r]=[1,r-l+1]\) 是最右的匹配段。考虑新的 \(i\)，如果满足 \(l\leq i\leq r\)，则 \(i\) 可以直接取 \(i-l+1\) 的答案继续扩展，否则继续扩展。最后更新区间。
点击查看代码
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
int n, m, z[1 << 26];
char a[1 << 26];
void exkmp(int len) {
z[1] = len;
debug("a = %s\n", a + 1);
for (int i = 2, l = 0, r = 0; i <= len; i++) {
if (i <= r) z[i] = min(z[i - l + 1], r - i + 1);
while (i + z[i] <= len && a[1 + z[i]] == a[i + z[i]]) ++z[i];
if (i + z[i] - 1 > r) r = i + z[l = i] - 1;
debug("z[%d] = %d\n", i, z[i]);
}
}
char buf[1 << 26];
int main(){
scanf("%s%s", buf + 1, a + 1);
n = strlen(a + 1), m = strlen(buf + 1);
a[n + 1] = '?';
for (int i = 1; i <= m; i++) a[n + i + 1] = buf[i];
exkmp(n + m + 1);
LL sum1 = n + 1, sum2 = 0;
for (int i = 2; i <= n; i++) sum1 ^= 1ll * i * (z[i] + 1);
for (int i = 1; i <= m; i++) sum2 ^= 1ll * i * (z[i + n + 1] + 1);
printf("%lld\n", sum1);
printf("%lld\n", sum2);
return 0;
}