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

[题目]kuangbin带你飞KMP A

思路

模板题，注意尽量用scanf输入，直接cin会超时，这里我取消了同步。

AC代码

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

int P[MAXN];
int T[MAXN];
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;
    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--){
        int N,M;
        cin>>N>>M;
        for(int i = 0 ;i<N;i++){
            cin>>T[i];
        } 
        for(int i = 0 ; i < M ; i++){
            cin>>P[i];
        }
        tlen = N;
        plen = M;
        int ans;
        ans=KMP_Index();
        if(ans==-1) 
            cout<<ans<<"\n";
        else cout<<ans+1<<"\n";
         
        
    }
        
    return 0;
}