约定：本文字符串均从 \(1\) 开始。模式串 \(T\) 的长度为 \(n\)，匹配串 \(S\) 的长度为 \(m\)。
1. KMP
1.1 前缀函数
给定一个长度为 \(n\) 的字符串 \(S\)，其前缀函数被定义为一个长度为 \(n\) 的数组 \(\pi\)。其中 \(\pi_i\) 被定义为：
- 若子串 \(S[1\cdots i]\) 有一对相等的真前缀与真后缀（即除了该子串本身的前缀和后缀）则 \(\pi_i=i\)，即为该真前缀的长度；
- 如果不只有一个相等的，那么 \(\pi_i\) 就是其中最长的那一对的长度；
- 如果没有相等的，那么 \(\pi_i=0\)。
劝退地，
特别地，\(\pi_1=0\)。
1.2 计算前缀函数
考虑如何计算 \(\pi(T)\)。
假设我们已经求出了 \(\pi_1\sim\pi_{i-1}\)，令 \(\pi_{i-1}=j\)，若 \(T[j+1]=T[i]\)，根据前缀函数的定义，可以得到 \(T[1\cdots j+1]=T[i-j\cdots 1]\)，则 \(\pi_i=j+1\)；否则，\(j\leftarrow \pi_j\)，继续判断直到 \(j=0\)，此时 \(\pi_i=0\)。
1.3 KMP 匹配
得到模式串 \(T\) 的前缀函数后，可以用与之类似的方式将其与 \(S\) 进行匹配：假设已经匹配完 \(S[i-1]\)，对应的 \(T\) 中的字符为 \(T[j]\)，若 \(S[i]=T[j+1]\)，则可以继续匹配；否则 \(j\leftarrow \pi_j\)，根据前缀函数的定义可得 \(T[\pi_j]=T[j]=S[i-1]\)，继续判断直到 \(j=0\)，此时从头开始匹配。
若 \(j=n\)，说明匹配完成，则与之第一个匹配的位置为 \(S[i-n+1]\)。
时间复杂度 \(O(n+m)\)。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e6+10;
char T[N], S[N];
int n, m, ne[N]; // ne为T的前缀函数
void get_next() { // 求ne数组(即前缀函数)
ne[1] = 0;
for (int i = 2, j = 0; i <= n; ++i) {
while (T[j+1] != T[i] && j) j = ne[j];
if (T[j+1] == T[i]) ne[i] = ++j;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> S+1 >> T+1;
n = strlen(T+1), m = strlen(S+1);
get_next();
for (int i = 1, j = 0; i <= m; ++i) { // 匹配
while (T[j+1] != S[i] && j) j = ne[j];
if (T[j+1] == S[i]) ++j;
if (j == n) cout << i-n+1 << '\n', j = ne[j];
}
for (int i = 1; i <= n; ++i) cout << ne[i] << ' ';
cout << '\n';
return 0;
}
2. exKMP
2.1 Z 函数
给定一个长度为 \(n\) 的字符串 \(S\)，定义其 Z 函数 \(z(i)\) 表示 \(S\) 和 \(S[i,n]\)（即以 \(S[i]\) 开头的后缀）的最长公共前缀（LCP）的长度。
劝退地，
特别地，\(z(1)=n\)。
2.2 计算 Z 函数
考虑如何计算 \(T\) 的 Z 函数。
对于 \(i\)，我们称区间 \([i,i+z(i)-1]\) 为 \(i\) 的匹配段，也称作 Z-box。我们需要维护最靠右的 box，记作 \([l,r]\)，初始时 \(l=r=0\)。根据定义，可得 \(s[l\cdots r]=s[1\cdots r-l+1]\)。
假设我们已经求出了 \(z(1)\sim z(i-1)\)。则：
- 若 \(i\le r\)：根据 \([l,r]\) 的定义，有 \(s[i\cdots r]=s[i-l+1\cdots r-l+1]\)，因此 \(z(i)\ge \min(z(i-l+1),r-i+1)\)。这时：
- \(z(i-l+1)<r-i+1\)：即 \(i+z(i)-1\) 对应的位置在 box 内，则 \(z(i)=z(i-l+1)\)。
- \(z(i-l+1)\ge r-i+1\)：即 \(i+z(i)-1\) 对应的位置在 box 外，则 \(z(i)\leftarrow z(i-l+1)\)，然后暴力枚举能够扩展的字符即可。
- 若 \(i>r\)：暴力枚举能够扩展的字符。
计算完 \(z(i)\) 后更新 \(l,r\)。
2.3 exKMP 匹配
与计算 Z 函数的过程类似，但我们是在 \(S\) 上计算。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 2e7+10;
char T[N], S[N];
int n, m, z[N], p[N];
ll get_num(int a[], int n) {
ll ans = 0;
for (int i = 1; i <= n; ++i) ans ^= (ll)i * (a[i]+1);
return ans;
}
void get_z() { // 计算z函数
z[1] = n;
for (int i = 2, l = 0, r = 0; i <= n; ++i) {
if (i < r) z[i] = min(z[i-l+1], r-i+1);
while (z[i] <= n-i && T[i+z[i]] == T[1+z[i]]) z[i] ++;
if (i+z[i]-1 > r) r = i+z[i]-1, l = i;
}
}
void get_p() { // 计算p函数
for (int i = 1, l = 0, r = 0; i <= m; ++i) {
if (i < r) p[i] = min(z[i-l+1], r-i+1);
while (p[i] <= m-i && S[i+p[i]] == T[1+p[i]]) p[i] ++;
if (i+p[i]-1 > r) r = i+p[i]-1, l = i;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> S+1 >> T+1;
n = strlen(T+1), m = strlen(S+1);
get_z(), get_p();
cout << get_num(z, n) << '\n' << get_num(p, m) << '\n';
return 0;
}