HDU1711 ——Number Sequence（KMP模板题）

Given two sequences of numbers : a[1], a[2], …… , a[N], and b[1], b[2], number K which make a[K] = b[1], a[K + 1] = b[2], …… , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.

Input

The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], …… , a[N]. The third line contains M integers which indicate b[1], b[2], …… , b[M]. All integers are in the range of [-1000000, 1000000].

Output

For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

Sample Input

2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1

Sample Output

6
-1

代码：

#include <iostream>
#include <cstdio>


using namespace std;

int next1[10005];
int board[10005];
int str[1000005];//寻找str串中是否有board串。
int N,M;//分别是str和board中串的长度。

void getNext(){

    int k = -1;
    int j = 0;
    next1[0] = -1;//next数组最好是从0开始要不然会很麻烦 
    while(j<M){
        if(k == -1 || board[j] == board[k]){
            if(board[j+1] == board[k+1]){ 
                next1[++j] = next1[++k];
            }
            else next1[++j] = ++k;
        }
        else {
            k = next1[k];
        }
    }
}



int Find(){//返回匹配到的位置 
    getNext();//当str多次更改而board不变时可以拿出去，因为next数组只与所找的串有关。
    int temp1 = 0,temp2 = 0;
    while(temp1<N && temp2<M){
        if(temp2 == -1 || str[temp1] == board[temp2]){
            temp1++;temp2++;
        }
        else{
            temp2 = next1[temp2];
        }
    } 
    if(temp2 == M)return temp1-temp2;
    else return -1;  
}

int main(){

    int T;
    cin>>T;
    while(T--){
        scanf("%d %d",&N,&M);
        for(int i=0 ; i<N ; i++)scanf("%d",&str[i]); 
        for(int i=0 ; i<M ; i++)scanf("%d",&board[i]);//这里和next数组统一也从0开始 
        int re = Find();
        if(re == -1)printf("-1
");
        else printf("%d
",re+1);//由于前面是从0开始而题中是从1开始所以这里加1 
    }

    return 0;
}