题解 | String Matching

// KMP算法, 下标从1开始，s为主串，长度为m，p为模式串，长度为n
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 7;

char s[N], p[N];
int ne[N];

signed main(){
    cin >> s + 1 >> p + 1;
    int m = strlen(s + 1);
    int n = strlen(p + 1);

    ne[1] = 0;
    for(int i = 2, j = 0;i <= n;i ++){
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }

    int cnt = 0;
    for(int i = 1, j = 0;i <= m;i ++){
        while(j && s[i] != p[j + 1]) j = ne[j]; 
        if(s[i] == p[j + 1]) j ++;
        if(j == n){
            cnt ++;
            j = ne[j];
        }
    }

    cout << cnt << endl;
    return 0;
}