kmp算法：
1 kmp是用来匹配字符串，只能够匹配单一的字符串
2 kmp的算法的过程：
1：假设文本串的长度为n，模式串的长度为m；
2：先例用O(m)的时间去预处理next数组，next数组的意思指的是当前的字符串匹配失败后要转到的下一个状态；
3：利用o(n)的时间去完成匹配；
3 时间复杂度为o(n+m)即o(n)；
代码：
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 1000010
int t , n , m;
int text[MAXN];/*文本串*/
int pattern[MAXN];/*模式串*/
int next[MAXN];/*next数组*/
/*O(m)的时间求next数组*/
void getNext(){
next[0] = next[1] = 0;
for(int i = 1 ; i < m ; i++){
int j = next[i];
while(j && pattern[i] != pattern[j])
j = next[j];
next[i+1] = pattern[i] == pattern[j] ? j+1 : 0;
}
}
/*o(n)的时间进行匹配*/
void find(){
int j = 0;/*初始化在模式串的第一个位置*/
for(int i = 0 ; i < n ; i++){/*遍历整个文本串*/
while(j && pattern[j] != text[i])/*顺着失配边走，直到可以匹配，最坏得到情况是j = 0*/
j = next[j];
if(pattern[j] == text[i])/*如果匹配成功继续下一个位置*/
j++;
if(j == m){/*如果找到了直接输出*/
printf("%d\n" , i-m+2);/*输出在文本串中第一个匹配的位置，不是下标*/
return;
}
}
printf("-1\n");
}
int main(){
scanf("%d" , &t);
while(t--){
scanf("%d%d" , &n , &m);
for(int i = 0 ; i < n ; i++)
scanf("%d" , &text[i]);
for(int i = 0 ; i < m ; i++)
scanf("%d" , &pattern[i]);
getNext();
find();
}
return 0;
}
