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();
}

字符串模板

原文：https://www.cnblogs.com/Xiao-yan/p/15165532.html