Number Sequence

 1 #include<iostream>
 2 using namespace std;
 3 
 4 const int MAXM = 10000;
 5 const int MAXN = 1000000;
 6 
 7 int nextTable[MAXM];
 8 int pattern[MAXM];
 9 int text[MAXN];
10 
11 void GetNextTable(int m){
12     int j = 0;
13     nextTable[j] = -1;
14     int i = nextTable[j];
15     while(j < m){
16         if(i == -1 || pattern[j] == pattern[i]){
17             i++;
18             j++;
19             nextTable[j] = i;
20         }else{
21             i = nextTable[i];
22         }
23     }
24     return ;
25 }
26 int kmp(int n,int m){
27     GetNextTable(m);
28     int i = 0,j = 0;
29     while (i<n && j < m){
30         if(j == -1 || text[i] == pattern[j]){
31             i++;
32             j++;
33         }else{
34             j = nextTable[j];
35         }
36     }
37     if(j == m){  //匹配成功
38         return i - j + 1;
39     }else{
40         return -1;
41     }
42 }
43 int main(){
44     int caseNumber;
45     scanf("%d",&caseNumber);
46     while(caseNumber--){
47         int n,m;
48         scanf("%d%d",&n,&m);
49         for(int i = 0;i < n;i++){
50             scanf("%d",&text[i]);
51         }
52         for(int i = 0;i < m;i++){
53             scanf("%d",&pattern[i]);
54         }
55         printf("%d
",kmp(n,m));
56     }
57     return 0;
58 }