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;  
  
}

补充：软件开发 , C++ ,