题解 | #String Matching#

#include <iostream>
using namespace std;

const int N  = 1e6 + 10;
//注：以下数组下标从1开始
char p[N], s[N];
int ne[N];

void myNext(){//创建next数组
    int i = 2, j = 0;//ne[1]一定等于0，故i从2开始
    while(p[i]){
        while(j !=0 && p[i] != p[j+1]) j = ne[j];
        if(p[i] == p[j+1]) j ++;
        ne[i] = j;
        i ++;
    }
}

int main() {
    cin >> s+1 >> p+1;
    //创建next数组
    myNext();
    //KMP算法
    int i = 1, j = 0;
    int cnt = 0;
    while(s[i]){
        while(j != 0 && s[i] != p[j + 1]) j = ne[j];
        if(s[i] == p[j + 1]) j ++;
        if(!p[j + 1]){
            cnt++;
            j = ne[j];//继续新的匹配
        }
        i ++;
    }
    cout << cnt << endl;
    return 0;
}