【题目来源】
https://acm.hdu.edu.cn/showproblem.php?pid=1711

【题目描述】
Given two sequences of numbers : a[1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a 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.
译文：给定两个序列：a[1]、a[2]……、a[N]，以及 b[1]、b[2]……、b[M]（1 <= M <= 10000，1 <= N <= 1000000）。你的任务是找到一个数 K，使得 a[K] = b[1]、a[K + 1] = b[2]、……、a[K + M - 1] = b[M]。如果有多个这样的 K 值存在，则输出其中最小的那个。

【输入格式】
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].
译文：输入的第一行是一个整数 T，它表示测试案例的数量。每个测试案例包含三行。第一行有两个整数 N 和 M（1 <= M <= 10000，1 <= N <= 1000000）。第二行包含 N 个整数，表示数组 a 中的元素 a[1]、a[2]……、a[N]。第三行包含 M 个整数，表示数组 b 中的元素 b[1]、b[2]……、b[M]。所有整数的范围都在 [-1000000， 1000000] 之间。

【输出格式】
For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.
译文：对于每个测试案例，您都应输出一行内容，该内容仅包含上述描述的 K 值。若不存在这样的 K 值，则输出 -1 。

【输入样例】
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

【输出样例】
6
-1

【数据范围】
1<=M<=10000，1<=N<=1000000

【算法分析】
● 这是一道 KMP 算法的裸题。可参考：https://blog.csdn.net/hnjzsyjyj/article/details/160215718
● 题目给数字序列，就用数组 /vector<int>，绝对不要用命令 to_string(x) 转字符串！转字符串 = 必错 + 必超时。

【算法代码】

#include <iostream>
#include <vector>
using namespace std;

const int M=1e4+5;
int ne[M];

void getNext(vector<int> t) {
    int len=t.size();
    int i=0,j=-1;
    ne[0]=-1;
    while(i<len) {
        if(j==-1 || t[i]==t[j]) {
            i++,j++;
            ne[i]=j;
        } else j=ne[j];
    }
}

void KMP(vector<int> s,vector<int> t) {
    int lens=s.size(),lent=t.size();
    int i=0,j=0;
    while(i<lens && j<lent) {
        if(j==-1 || s[i]==t[j]) {
            i++,j++;
        } else j=ne[j];
    }
    if(j==lent) cout<<i-j+1<<endl;
    else cout<<-1<<endl;
}

int main() {
    int T;
    cin>>T;
    while(T--) {
        int n,m,x;
        cin>>n>>m;
        vector<int> s,t;

        for(int i=1; i<=n; i++) {
            cin>>x;
            s.push_back(x);
        }
        for(int i=1; i<=m; i++) {
            cin>>x;
            t.push_back(x);
        }

        getNext(t);
        KMP(s,t);
    }
    return 0;
}

/*
in:
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

out:
6
-1
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/160238859
https://blog.csdn.net/hnjzsyjyj/article/details/160215718
https://blog.csdn.net/hnjzsyjyj/article/details/160234350
https://blog.csdn.net/hnjzsyjyj/article/details/160228242
https://blog.csdn.net/hnjzsyjyj/article/details/160224665