代码
/*
* Project: 07_KMP
* File Created:Monday, January 4th 2021, 9:12:14 am
* Author: Bug-Free
* Problem: AcWing 831. KMP字符串
*/
// brute-force 暴力
// #include <iostream>
// using namespace std;
// const int N = 1e5 + 10, M = 1e6 + 10;
// int n, m;
// char S[M], P[N];
// int main() {
// cin >> m >> (P + 1) >> n >> (S + 1);
// for (int i = 1; i <= n - m + 1; i++) {
// bool flag = true;
// for (int j = 1; j <= m; j++) {
// if (S[i + j - 1] != P[j]) {
// flag = false;
// break;
// }
// }
// if (flag) {
// cout << i - 1 << " "; //题目中下标从0开始
// }
// }
// return 0;
// }
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
int n, m;
int ne[N];
char s[M], p[N];
void get_next() {
ne[1] = 0; //我们的下标从1开始, 题目中的下标从0开始
for (int i = 2, j = 0; i <= n; i++) {
while (j && p[i] != p[j + 1]) {
j = ne[j];
}
if (p[i] == p[j + 1]) {
j++;
}
ne[i] = j;
}
}
int main() {
cin >> n >> (p + 1) >> m >> (s + 1);
//求next数组
get_next();
// KMP匹配过程
for (int i = 1, j = 0; i <= m; i++) {
while (j && s[i] != p[j + 1]) {
j = ne[j];
}
if (s[i] == p[j + 1]) {
j++;
}
if (j == n) {
cout << i - n << " ";
j = ne[j];
}
}
return 0;
}
很棒!
大佬 cout<<i - n <<” ” ; 这个 为什么第一次是输出 初始位置呢?
初始化ne[1]=0, 这个加上之后确实好理解一些,类似递归求ne矩阵的感觉
我感觉字符串阿希还快吧。
kmp可以比字符串哈希知道一些额外信息
厉害啊大佬
您才是大佬hh
您放的最后一张图是我茅塞顿开(那张宠物的图 hh)