[kuangbin带你飞]专题十六 KMP & 扩展KMP &

题目

思路

模板题，做的和阅读题一样。。

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 = NEXT[j];
        }
    }
    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);
    int TT;
    cin>>TT;
    while(TT--){
        cin>>P>>T;
        tlen = T.length();
        plen = P.length(); 
        int ans;
        ans=KMP_Count();
        cout<<ans<<"\n";
         
        
    }
        
    return 0;
}