HDU-1711-Number Sequence

KMP模版

[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
using namespace std; 
#define N  1000005 
#define M 10005 
int a[N],b[M],nextt[M]; 
int n,m; 
void getnext() 
{ 
    int i,j; 
    i=0; 
    j=-1; 
    nextt[0]=-1; 
    while(i<m) 
    { 
        if(j==-1||b[i]==b[j]) 
        { 
            i++; 
            j++; 
            nextt[i]=j; 
        } 
        else 
        j=nextt[j]; 
    } 
} 
int kmp() 
{ 
    int i,j; 
    i=0; 
    j=0; 
    getnext(); 
    while(i<n) 
    { 
        if(j==-1||a[i]==b[j]) 
        { 
            i++; 
            j++; 
        } 
        else  
        j=nextt[j]; 
        if(j==m) 
        return i-j+1; 
    } 
    return -1; 
} 
int main() 
{ 
    int i,t,ans; 
    scanf("%d",&t); 
    while(t--) 
    {  www.2cto.com
        scanf("%d%d",&n,&m); 
        for(i=0;i<n;i++) 
        scanf("%d",&a[i]); 
        for(i=0;i<m;i++) 
        scanf("%d",&b[i]); 
        ans=kmp(); 
        printf("%d\n",ans); 
    } 
    return 0; 
}