Kmp

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
void get_next(char x[],int n,int nxt[]) {
    int i = 0, j = nxt[0] = -1;
    while (i < n) {
        while (j != -1 && x[i] != x[j]) j = nxt[j];
        nxt[++i] = ++j;
    }
}
char str[maxn],str1[maxn];
int nxt[maxn],ans;
void kmp(char x[],int n,char y[],int m) {
    int i = 0, j = 0;
    while (i < m) {
        while (j != -1 && y[i] != x[j]) j = nxt[j];
        i++;
        j++;
        if (j >= n) {
            ans++;
            j=0;
            //j = nxt[j];
        }
    }
}
int main() {
    cin >> str;
    cin >> str1;
    int n = strlen(str);
    int m = strlen(str1);
    get_next(str, n, nxt);
    kmp(str, n, str1, m);
    cout << ans << endl;
//    for (int i = 0; i < n; i++) {
//        cout << nxt[i] << " ";
//    }
}

Kmp

原文：https://www.cnblogs.com/Accpted/p/13086061.html