数据结构实验之串三：KMP应用（KMP模板）

AC_Code:
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <map>
 6 #include <stack>
 7 using namespace std;
 8 typedef long long ll;
 9 const int maxn=1e6+10;
10 int str1[maxn],str2[maxn],n,m,Next[maxn];
11 void find_next()
12 {
13     int i=0,j=-1;
14     Next[0]=-1;
15     while(i<m)
16     {
17         if( j==-1 || str2[i]==str2[j])
18         {
19             i++;
20             j++;
21             Next[i]=j;
22         }
23         else j=Next[j];
24     }
25 }
26 
27 int kmp(int x,int y)
28 {
29     if( n==0 || m==0 ) return -1;
30     int i=x,j=y;
31     while(i<n&&j<m)
32     {
33         if(j==-1|| str1[i]==str2[j])
34         {
35             i++;
36             j++;
37         }
38         else j=Next[j];
39     }
40     if( j==m ) return i-j+1;
41     else return -1;
42 }
43 
44 int main()
45 {
46     scanf("%d",&n);
47     for(int i=0;i<n;i++) scanf("%d",&str1[i]);
48     scanf("%d",&m);
49     for(int j=0;j<m;j++) scanf("%d",&str2[j]);
50     find_next();
51     int t1=kmp(0,0);
52     if( t1==-1 ) printf("-1
");
53     else
54     {
55         int t2=kmp(t1,0);
56         if( t2==-1 ) printf("%d %d
",t1,t1+m-1);
57         else printf("-1
");
58     }
59     return 0;
60 }