KMP模板
C++ 代码
#include"bits/stdc++.h"
using namespace std;
const int N = 1e6+ 5;
char p[N],s[N];
int ne[N];
int main() {
int n,m;
cin >> m >> p >> n >> s;
ne[0] = -1;
int k = -1;
for(int i = 1; i<m; i++) {
while(k != -1 && p[k+1] != p[i]) k = ne[k];
if(p[k+1] == p[i]) k++;
ne[i] = k;
}
int i = 0, j = 0;
while(i < n) {
while(j > 0 && p[j] != s[i]) j = ne[j-1] + 1;
if(p[j] == s[i]) j++;
if(j == m) {
printf("%d ", i - m + 1);
j = ne[j-1] + 1;
}
i++;
}
return 0;
}