虽然说原理很好理解，但是代码理解了花费我一个下午的时间，脑阔痛
该注释的地方都标记了，希望以后看到这些代码我还能好好理解吧
学习的链接地址：https://www.cnblogs.com/teble/p/7280575.html
/* Number Sequence */ /*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. 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 <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define MAXN 1000050 using namespace std; //这道题看得出来需要使用到KMP排序 //虽然说我理解了排序原理，却不太懂得实现它 //对于我这种来说，最担心的的莫过于输入问题（所以最后干脆用int数组解决） int a[MAXN], b[10050], _next[10050]; int repeat, i, n; __int64 m; void makeNext() { int q=1;//模板b字符串的临时下标，作为比较的后一位 int k=0;//最大前后缀长度 _next[1]=0;//模板字符串第一个字符最大前后缀长度为0 while ( q<n )//遍历数组 { if ( k==0 || b[k]==b[q] )//符合条件 { ++k,++q;//同时+1，判断下一位 if ( b[q]!=b[k] ) _next[q]=k; else _next[q]=_next[k];//上下两句话改变next数组的值 } else k=_next[k];//如果不相等，将前标往前移动 } /*数据检查for ( k=1 ; k<=n ; k++ ) { cout<<b[k]<<' '; } cout<<endl; for ( k=1 ; k<=n ; k++ ) { cout<<_next[k]<<' '; } cout<<endl;*/ } int kmp() { int i, j; for ( i=1,j=1 ; i<=m&&j<=n ; ) { if ( j==0 || a[i]==b[j] ) ++i,++j; else j=_next[j];//如果不相等的话，将此时的j变小，相当于将b数组往右移动 //next数组提供，当a[]的后m个元素和b[]开头的前m个元素顺序相同时提供下标的服务 } if ( j==n+1 ) return i-n;//i是当前点，n是b[]的长度，返回的是初始点 else return -1;//j==n+1的原因是a[]都被遍历完了，而b[]仍未遍历完 //只有当b[]都被遍历完了才算完整结束 } int main(void) { scanf("%d", &repeat); while ( repeat-- ) { scanf("%I64d%d",&m ,&n); for ( i=1 ; i<=m ; i++ ) { scanf("%d", &a[i]); } for ( i=1 ; i<=n ; i++ ) { scanf("%d", &b[i]); } makeNext(); cout<<kmp()<<endl; } return 0; }