kmp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll N = 1e6 + 9;
const ll inf = 0x3f3f3f3f;
char a[N];
char b[N];
int ne[N];
void solve() {
scanf("%s", (a + 1));
scanf("%s", (b + 1));
int n = strlen(b + 1);
int m = strlen(a + 1);
for (int i = 2, j = 0; i <= n; i ++) {
while (j && b[i] != b[j + 1])j = ne[j];
ne[i] = (b[j + 1] == b[i]?++j:j);
}
for (int i = 1, j = 0; i <= m; i ++) {
while ( j && b[j + 1] != a[i])j = ne[j];
if (b[j + 1] == a[i])j++;
if (j == n) {
printf("%d\n", i-n + 1 );
}
}
for (int i = 1; i <= n; i ++) printf("%d ", ne[i]);
}
signed main() {
ll t = 1;//cin >> t;
while (t--) solve();
}
字符串模板