P3375 【模板】KMP字符串匹配

来一道模板题，直接上代码。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 5;

int n, m;

char s1[N], s2[N];

int nxt[N] ;

void Get_next(char *s) {

    int j, L = strlen(s + 1);

    nxt[1] = j = 0;

    for(int i = 2; i <= L; i++) {

        while(j && s[i] != s[j + 1]) j = nxt[j] ;

        if(s[i] == s[j + 1]) j++;

        nxt[i] = j;

    }

}

int main() {

    scanf("%s%s", s1 + 1, s2 + 1);

    Get_next(s2) ;

    int L1 = strlen(s1 + 1), L2 = strlen(s2 + 1) ;

    for(int i = 1, j = 0; i <= L1; i++) {

        while(j > 0 && (j == L2 || s1[i] != s2[j + 1])) j = nxt[j] ;

        if(s1[i] == s2[j + 1]) j++;

        if(j == L2) cout << i - L2 + 1 << '\n' ;

    }

    for(int i = 1; i <= L2; i++) cout << nxt[i] << ' ' ;

    return 0;

}