例题4.6 Number Sequence（书上默写，但在网站上运行超时）建议重做3次，|||

/*
分三步，主函数，kmp,求next数组
主函数就是输入输出
书上的代码默写
求next数组太恶心!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
*/

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXM = 10000;
const int MAXN = 1000000;


int pattern[MAXM];
int nexttable[MAXM];
int text[MAXN];

void Getnexttable(int m){
    int j=0;
    nexttable[j]=-1;
    int i=nexttable[j];

    while(j<m){

        if(-1==i||pattern[i]==pattern[j]){
            ++i;
            ++j;
            nexttable[j]=i;//得把数组j的每个位置都填上！！！！！！！！！！！！！！！！！
        }else{

            i=nexttable[i];//变态！！！！！！！！！！！！！！！！！！！！！！！

        }

    }
}


int KMP(int m,int n){

    Getnexttable(m);
    int i=0;//不应该是-1，不然就白跑了一趟
    int j=0;//不应该是-1，不然就白跑了一趟

    while(i<m&&j<n){
        if(-1==i||pattern[i]==text[j]){
            ++i;
            ++j;

        }else{

            i = nexttable[i];
        }
    }

//     if(i==m&&pattern[i]==text[j]){//不能这么写呀，不对，只到m-1
    if(i==m){
        return j-i+1;
    }else{
        return -1;
    }
}

int main(){
    int caseNumber;
    int m;
    int n;

    scanf("%d",&caseNumber);
    for(int i=0; i<caseNumber; ++i)
    {
        scanf("%d %d",&n,&m);


        for(int k=0; k<n; ++k)
        {
            scanf("%d",&text[k]);
        }

        for(int j=0; j<m; ++j)
        {
            scanf("%d",&pattern[j]);
        }

        printf("%d\n",KMP(m,n));

    }

}