【题目来源】
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 1out:
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