题解 | #String Matching#

//KMP查找C++写法
#include <iostream>
#include <vector>
using namespace std;

void getNext(vector<int>&next,string mode){
    //i代表前缀末尾，j代表后缀末尾
    int i =0 ,j;
    for(j = 1;j<next.size();j++){
        //如果不匹配的情况，i需要跳到前一个已经匹配的地方
        while(i>0 && mode[i] !=mode[j]){
            i = next[i-1];
        }
        //如果匹配的话让前缀末尾前进
        if(mode[i] == mode[j]){
            i++;
        }
        next[j] = i;//
    }
}

int countStr(string s,string mode,const vector<int>next){
    int result = 0;
    for(int i = 0,j =0;i<s.size();i++){
        //匹配结束的情况
        if(j == mode.size()-1 && s[i] == mode[j]){
            result++;
            j = next[j-1];//
        }
        //如果j>0且匹配结束
        while(j>0 &&s[i] != mode[j]){
            j = next[j-1];
        }
        j++;
    }
    return result;
}

int main() {
    string s,mode;
    cin>>s>>mode;
    vector<int>next(mode.size(),0);
    getNext(next,mode);
    cout<< countStr(s,  mode,next);
}
// 64 位输出请用 printf("%lld")