kmp&&hdu 1711 next數組

kmp這幾天一直都在搞這個，今天A了hdu的1711這題，就是簡單的kmp模板題；

kmp的核心就是next數組；這幾天一直在看嚴蔚敏的數據結構課本，上面介紹的是

next[j]={

                 0,j==1,

max{k| 1<k<j,且P1P2'……Pk-1==Pj-k+1........Pj-1}，

1，

}

next[j]表示1到k-1中最長首尾重復子串的長度+1，也就是當模式串的第[j]個和文本串中的第[i]個不匹配時，主串指針i不用回溯，而只需模式串的j=next[j],假設文本串是S,模式串是P則下次S[i]和P[next[j]]比較，j應該回溯到next[j];
 

 
#include<stdio.h>   
#include<iostream>   
#include<cmath>   
#include<algorithm>   
#include<string>   
#include<vector>   
#include<cstring>   
using namespace std;  
const int N=1000003;  
int next[N];  
int a[N],b[N];  
void getNext( int str[], int pos ,int len) {  
  
    if(next == NULL || str == NULL )  
        return ;  
  
        next[0] = -1;  
  
        int i=pos,j=-1;  
  
        while( i < len) {  
  
            if(j == -1 || str[i] == str[j]) {  
                i++;  
                j++;  
                next[i] = j;//   
            }  
            else {  
                j=next[j];  
            }  
        }  
}  
int main()  
{  
//freopen("1.txt","r",stdin);   
//freopen("2.txt","w",stdout);   
     int T;  
    scanf("%d",&T);  
    while(T--){  
        int n,m;  
        scanf("%d%d",&n,&m);  
        for(int i=0;i<n;i++){  
            scanf("%d",&a[i]);  
  
        }  
        for(int i=0;i<m;i++) {  
            scanf("%d",&b[i]);  
        }  
        getNext(b,0,m);  
        int i=0,j=0;  
        while(i<n && j<m ){  
            if(j == -1 || a[i] == b[j]){  
                i++;  
                j++;  
            }  
            else{  
                j=next[j];  
            }  
        }  
        if(j==m){  
            printf("%d\n",i-m+1);  
        }else{  
            printf("-1\n");  
        }  
    }  
    return 0;  
  
}