kmp这几天一直都在搞这个，今天A了hdu的1711这题，就是简单的kmp模板题；

kmp的核心就是next数组；这几天一直在看严蔚敏的数据结构课本，上面介绍的是

next[j]={

0,j==1,

max{k| 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   
#include   
#include   
#include   
#include   
#include   
#include   
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