什么是exKMP
exKMP(Z-Algorithm) 是一个可以在 \(O(|S|+|T|)\) 的时间复杂度内求出
- \(T\) 串的每个后缀与 \(T\) 的 LCP（最长公共前缀）
- \(T\) 串和 \(S\) 串每个后缀的 LCP。
的算法。
算法过程
首先回忆一下 KMP 算法，求 \(nxt\) 数组和两串匹配本质上没啥区别。
所以我们尝试也将上述俩问题，即 \(T-T\) 和 \(T-S\) 变成一个问题。
先解决第一个问题：令 \(z_x\) 为 \(\max\limits_{i=1}^{ |T| - x + 1}\{T_{1\sim i}=T_{x\sim x + i - 1}\}\)，那么答案就是 \(z\) 数组。
如何求出？
先看下图：令 \(L\) 为满足 \(k+Z_k-1=\max\limits_{j=1}^{i-1}j+Z_j-1\) 的 \(k\)。
根据 \(z\) 的定义，我们有 \(T_{1\sim Z_L}=T_{L\sim L+Z_L-1}\land T_{Z_L+1}\neq T_{L+Z_L}\)
所以有 \(T_{i\sim L+Z_L-1}=T_{i-L+1\sim Z_L}\)
再根据 \(z\) 的定义，有 \(T_{1\sim Z_{i-L+1}}=T_{i-L+1\sim i-L+1+Z_{i-L+1}-1}\)
这时候有两种情况：
-
\(Z_{i-L+1}\le R-i+1\)，显然 \(Z_i=Z_{i-L+1}\)。
-
\(Z_{i-L+1}>R-i+1\)，那么因为 \(Z_i\) 最多也就是 \(R-i+1\)（因为 \(T_{L+Z_L-i+1}=T_{Z_L+1}\neq T_{L+Z_L}\)），所以 \(Z_i=R-i+1\)
所以有 \(Z_i=\min(R-i+1,Z_{i-L+1})\)。
但是，上述的计算都是基于 \(R\ge i\) 来说的。
否则呢？
直接暴力匹配即可。
时间复杂度呢？
注意到暴力匹配的字符的 \(z\) 和一定不超过 \(n\) （因为 \(z\) 匹配到哪，下一次至少从那开始暴力匹配），所以仍为线性的。
然后 \(T-S\) 的思路和上面的 \(T-T\) 是一样的，不再赘述。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e7 + 5;
char s[N], t[N];
int z[N], p[N], n, m;
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> s + 1 >> t + 1;
n = strlen(s + 1);
m = strlen(t + 1);
z[1] = 1;
int l = 0, r = 0;
for(int i = 2; i <= m; i ++)
{
if(r >= i) z[i] = min(r - i + 1, z[i - l + 1]);
while(t[z[i] + 1] == t[i + z[i]] && i + z[i] <= m) z[i] ++;
if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}
l = r = 0;
for(int i = 1; i <= n; i ++)
{
if(r >= i) p[i] = min(r - i + 1, z[i - l + 1]);
while(t[p[i] + 1] == s[i + p[i]] && i + p[i] <= n) p[i] ++;
if(i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
}
return 0;
}