扩展KMP算法及其应用
给定两个字符串 (S) 和 (T)，长度分别为 (n) 和 (m)。要求计算两个数组 (A) 和 (B)：
- \(A\) 存储 \(T\) 的每个后缀与 \(T\) 的最长公共前缀（LCP）长度。
- \(B\) 存储 \(S\) 的每个后缀与 \(T\) 的最长公共前缀长度。
设数组 (matchLen[i]) 表示 (S[i \dots n-1]) 与 (T) 的最长公共前缀长度，则 (matchLen) 即为所求的 (B)。
为了高效地计算 (matchLen)，我们引入辅助数组 (selfMatch[j])，表示 (T[j \dots m-1]) 与 (T) 的最长公共前缀长度。
考虑以下样例：
假设已知 (matchLen[0])，如果直接暴力计算 (matchLen[1])，则需要重新扫描大部分字符串，效率低下。因此，我们需要优化以避免重复扫描。
使用扩展 KMP（Z 函数），我们可以有效减少不必要的比较次数。接下来分析两种主要情况：
情况一：当 (k + selfMatch[k-pivot] < pivot + matchLen[pivot])
在这种情况下，由于之前的部分已经匹配成功，可以直接利用已知信息来填充部分 (matchLen) 值。
if (idx + selfMatch[idx - pivot] < pivot + matchLen[pivot]) {
matchLen[idx] = selfMatch[idx - pivot];
}
情况二：当 (k + selfMatch[k-pivot] >= pivot + matchLen[pivot])
此时，部分字符已经匹配，但还需要进一步验证剩余字符是否匹配。
int extendLen = min(pivot + matchLen[pivot] - idx, 0LL);
while (idx + extendLen < n && extendLen < m && S[idx + extendLen] == T[extendLen]) ++extendLen;
matchLen[idx] = extendLen; pivot = idx;
最后，还需计算 (selfMatch) 数组，其逻辑类似于计算 (matchLen)。
完整代码如下：
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 2e6 + 5;
char S[MAXN], T[MAXN];
int selfMatch[MAXN], matchLen[MAXN];
void computeSelfMatch(const char *str, int len, int *arr) {
arr[0] = len;
for (int i = 1, l = 0, r = 0; i < len; ++i) {
if (i <= r && arr[i - l] < r - i + 1) arr[i] = arr[i - l];
else {
arr[i] = max(0, r - i + 1);
while (i + arr[i] < len && str[arr[i]] == str[i + arr[i]]) ++arr[i];
}
if (i + arr[i] - 1 > r) l = i, r = i + arr[i] - 1;
}
}
void extendedKMP(const char *base, const char *pattern, int baseLen, int patLen) {
computeSelfMatch(pattern, patLen, selfMatch);
for (int i = 0, l = 0, r = 0; i < baseLen; ++i) {
if (i <= r && selfMatch[i - l] < r - i + 1) matchLen[i] = selfMatch[i - l];
else {
matchLen[i] = max(0, r - i + 1);
while (i + matchLen[i] < baseLen && matchLen[i] < patLen && base[i + matchLen[i]] == pattern[matchLen[i]]) ++matchLen[i];
}
if (i + matchLen[i] - 1 > r) l = i, r = i + matchLen[i] - 1;
}
}
int main() {
cin >> S >> T;
int n = strlen(S), m = strlen(T);
extendedKMP(S, T, n, m);
// 输出结果...
return 0;
}
