题目

思路

改一下kmp模板就行了
在匹配到的时候，j不用回到next[j]，直接从0开始。

AC代码

#include<iostream>
using namespace std;
const int MAXN=10000002;

string P;
string T;

int NEXT[MAXN];
int plen,tlen;
void getNEXT(){
    int k,j;
    k = -1;j = 0;NEXT[0] = -1;
    while(j<plen){
        if(k==-1||P[k] == P[j]){
            NEXT[++j] = ++k; 
            if(P[j] == P[k]){
                NEXT[j] = NEXT[k];
            }
        }else{
            k=NEXT[k];
        }
    }
    
}



int KMP_Count(){
    int ans = 0;
    int i = 0;
    int j = 0;
    getNEXT();
    while(i<tlen){
        if(j==-1||T[i] == P[j]){
            i++;
            j++;
//          cout<<"j = "<<j<<endl;      
        }else
        {
            j = NEXT[j];
        }
        if(j == plen){
            ans ++;
            j = 0;
        }
    }
    return ans;
}


int KMP_Index()
{
    int i = 0, j = 0;
    getNEXT();

    while(i < tlen && j < plen)
    {
        if(j == -1 || T[i] == P[j])
        {
            i++; j++;
        }
        else
            j = NEXT[j];
    }
    if(j == plen)
        return i - plen;
    else
        return -1;
}

int main(){
    
    ios::sync_with_stdio(false);
        while(cin>>T&&"#"!=T){
            cin>>P;
            tlen = T.length();
            plen = P.length(); 
            int ans;
            ans=KMP_Count();
            cout<<ans<<"\n";
        }
        
         
        
    
    return 0;
}