概览
基于前缀的字符串匹配
题解
kmp: 匹配的模板串,前缀与后缀相等所以可以移动位置
1. 约定从1开始
2. ne[i]=j: p[1,..j]=p[i-j+1,i];
3. 基准: i-1与j匹配, i与j+1不匹配
- 失配:
失配时最少移动距离,新的已匹配下标就是ne[j]; 然后再看下一个点i与j+1是否匹配,如果不匹配,继续失配递归处理
- 匹配
代码
#include <iostream>
using namespace std;
const int N = 10010, M = 100010;
int n, m;
char p[N], s[M];
int ne[N]; // p[1,..,j] == p[i-j+1, ..., i]
int main() {
cin >> n >> p + 1 >> m >> s + 1; // n是模板串p长度, m是待匹配串s长度
// 求next数组过程 ne[1] = 0;
// 怎么求?想法就是只有知道ne[1],其实ne是递归由小到大生成的。
// 所以只需要找到当失配时,就一直找;
// 最终找到匹配的位置,也就是ne的含义
for (int i = 2, j = 0; i <= n; i ++) { // i与j+1匹配,i是为了求ne数组; j是匹配位置
while(j && p[i] != p[j + 1]) j = ne[j];
// quit 1
if (p[i] == p[j + 1]) j ++; // 到达 p[1, .. j] = p[i-j+1, i]
// quit 2
// j == 0 ? 不用处理,因为每次循环比较的是i与j+1
ne[i] = j; // 添加上已记录的结果
}
// 匹配过程: i与j+1匹配
for (int i = 1, j = 0; i <= m; i ++) {
while (j && s[i] != p[j + 1]) j = ne[j]; // 如果j已经退到最后
if (s[i] == p[j + 1]) j ++;
if (j == n) { // 匹配成功
printf("%d ", i - n);
}
}
return 0;
}