#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 998244353;
int n, m, ne[N];
char a[N], b[N]/*母*/;
int main() {
scanf("%d%s%d%s", &n, a + 1, &m, b + 1);
for (int i = 2, j = 0; i <= n; ++i) {
while (j && a[i] != a[j + 1]) j = ne[j];
if (a[i] == a[j + 1]) j++;
ne[i] = j;
}
for (int i = 1, j = 0; i <= m; ++i) {
while (j && b[i] != a[j + 1])j = ne[j];
if (b[i] == a[j + 1]) j++;
if (j == n) {
printf("%d ", i - n);
j = ne[j];
}
}
return 0;
}
【模板】KMP
发布于 2022-08-10 7 次阅读
Comments NOTHING