AcWing 831. KMP字符串
原题链接
简单
作者:
szywdwd
,
2021-05-21 15:26:27
,
所有人可见
,
阅读 205
// // 暴力字符串匹配法,复杂度为O(NM)
// #include <iostream>
// #include <string>
// using namespace std;
// int main()
// {
// int lengthOfPattern, lengthOfString;
// string Pattren, String;
// cin >> lengthOfPattern >> Pattren >> lengthOfString >> String;
// for(int i = 0; i <= lengthOfString - lengthOfPattern; ++i) {
// bool flag = false;
// for(int j = 0; j < lengthOfPattern; ++j) {
// if(Pattren[j] != String[j + i]) {
// flag = true;
// break;
// }
// }
// if(flag == false) cout << i << ' ';
// }
// return 0;
// }
// kmp算法下标一致从1开始
#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
int main()
{
cin >> n >> p + 1 >> m >> s + 1;
// 求next数组,next[1]必为0,故从下标2开始求
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;
}
// 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)
{
printf("%d ", i - n);
j = ne[j];
}
}
return 0;
}