AcWing 831. KMP字符串
原题链接
简单
作者:
瞳星结
,
2021-06-08 21:45:33
,
所有人可见
,
阅读 264
//援引自y总代码评论区,感觉易读性更好一丢丢,记录下来,方便以后看
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
int ne[N];
int n, m;
char p[N], s[M];
int main() {
cin >> n >> p >> m >> s;
for (int i = 1, j = 0; i < n; i++) {
while (j && p[i] != p[j]) j = ne[j - 1];//当i和j不等,即j-1处匹配成功,则j = ne[j - 1]
if (p[i] == p[j]) j++; //检查p[i] == p[j],防止j==0的情况
ne[i] = j;
}
//与长字符串匹配i从0开始
for (int i = 0, j = 0; i < m; i++) {
while (j && s[i] != p[j]) j = ne[j - 1];
if (s[i] == p[j]) {
j++;
if (j == n) {
cout << i - n + 1 << " ";
j = ne[n - 1];
}
}
}
return 0;
}