题解 | #String Matching#

#include <iostream>
using namespace std;
int nextt[1000000];
string a,b;//文本串，模式串

void GetNext(int m)
{
    nextt[0]=-1;
    int i=-1;
    int j=0;
    while(j<m)
    {
        if(i==-1||b[i]==b[j])
        {
            i++;j++;
            nextt[j]=i;
        }
        else {
            i=nextt[i];
        }
    }
}
int KMP(int m,int n)
{
    int i=0;//文本串
    int j=0;//模式串
    int num=0;
    GetNext(m);
    while(i<n)
    {
        if(a[i]==b[j]||j==-1)
        {
            i++;j++;
        }
        else {
            j=nextt[j];
        }
        if(j==m)//模式串的下标最大为m-1，j必须重新赋值
        {
            num++;
            j=nextt[j];
        }
    }
    return num;
}

int main() {
    while (cin >> a >> b) { 
        int n=a.size();
        int m=b.size();
        int num=KMP(m,n);
        cout<<num<<endl;
    }
}