题目描述
blablabla
样例
blablabla
$O(n)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
const int N = 100010 ,M=1000010;
int ne[N];
char p[N], s[M];
int n, m;
int main(){
cin >> n >> p + 1 >> m >> s + 1;
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;
}
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;
}
所以要存下 p 的每个ne[];
然后对 s 找:
两个指针分别指向 s 和 p ,循环直到遇到s[i] != p[j+1], j 就要跳到下一个ne[j]
如果s[i] == p[j+1],指针就移动到下一位
到 j指针最后指到 s 的末尾,j返回到 ne[j]