题意：给出t个例子，对于每个例子有两个数字序列p,q，长度为n,m 然后对应输入相应个数的数字，范围：[-1000000, 1000000]你求p对q的最小匹配位置 如果没有则输出-1；
思路：
由于是我做的kmp专题第一道题，所以顺便记录一下自己对于kmp学习理解过程：
先尝试使用暴力过题，也就是 逐一匹配，不符合则均往后移否则 主字符串回到开始匹配位的下一位，子字符串回到开头。
// i = j = k = 0;
// while(i<len1&&j<len2){ // if(num[i]==num1[j]){ // i++; // j++; // }else{ // i++; // k++; // j = 0; // i = k; // } // if(j==len2) ans = i-j+1; // }
这样时间复杂度会很高，所以会超时
为了尽可能减少复杂度（通过匹配时尽可能子字符串往有效的位置移动）所以就引入了next[]数组，（作为记录前缀与后缀相同的最大长度）
所以涉及next数组求法，至于原理就不写了（等刷完该专题再来总结），直接写模板：同时要注意因为在C++中next[]在提交中编译是不成功的，所以用换个名字nex[].
void getnex(){ int i=0,j=-1; nex[i]=j; while(i<len2){ if(j==-1||num1[i]==num1[j]){ i++;j++; nex[i]=j; } else j=nex[j]; } }
kmp 求最小匹配位置：
int kmp(){ int i = 0, j = 0; getnex(); while(i < len1 && j < len2) { if(j == -1 || a[i] == b[j]) { i++; j++; } else j = nex[j]; } return (j==len2)?(i -len2 + 1):-1; }
最后完整代码：(其中对于cin一定要添加加速指令否则会超时，cin读取速度比较慢)
#include <iostream> #include <cstdio> using namespace std; const int maxn = 1e4+10; int num[100*maxn];//主 int num1[maxn]; int nex[maxn]; int N,M; int k,len1,len2,ans=-1; //求子字符串的nex数组 void getnex(){ int i=0,j=-1; nex[i]=j; while(i<len2){ if(j==-1||num1[i]==num1[j]){ i++;j++; nex[i]=j; } else j=nex[j]; } } int KMP(){ int i = 0, j = 0; getnex(); while(i < N && j < M) { if(j == -1 || num[i] == num1[j]) { i++; j++; } else j = nex[j]; } if(j == M) return i -M + 1; else return -1; } int main(){ ios::sync_with_stdio(0); cin.tie(0); int T; cin>>T; while(T--){ cin>>N>>M; for(int i=0;i<N;i++) cin>>num[i]; for(int i=0;i<M;i++) cin>>num1[i]; len1 = N ,len2 = M; ans = KMP(); cout<<ans<<endl; } }