kmp算法c++代码实现

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 #define max 5000
 5 
 6 int t[max];//目标串
 7 int p[max];//模式串
 8 int next[max];//前缀函数
 9 int n,m;//n为目标串的数目，m为模式串的数目
10 void function_prefix(int *s,int *next)
11 {
12  next[1]=next[0]=0;//显然为0，无字符或者只有一个字符它的前缀显然为0
13  int q=0;
14  for(int i=2;i<=m;i++)
15  {
16     while(q>0&&s[q+1]!=s[i])//当匹配不成功时
17         q=next[q];//这一步好好想想就明白了
18     if(s[q+1]==s[i])
19         q++;
20      next[i]=q;//确定i的前缀
21  }
22 }
23 int kmp(int*t,int *p,int *next)
24 {
25     function_prefix(p,next);
26     int k=0;
27     for(int i=1;i<=n;i++ )//for循环可以从i=0开始
28     {
29         while(k>0&p[k+1]!=t[i])
30             k=next[k];//好好想想
31         if(p[k+1]==t[i])
32             k++;
33         if(k==m) return i-m;//如果for循环是从i=0开始应该返回i-m+2;
34     }
35     return -1;
36 }
37 int main ()
38     {
39     int s;
40     scanf ("%d",&s);
41     while (s--)
42     {
43         scanf ("%d %d",&n,&m);
44         for (int i=0;i<n;i++)
45           cin>>t[i];
46         for (int i=0;i<m;i++)
47            cin>>p[i];
48         int ans=kmp (t,p,next);
49         cout<<ans;
50     }
51     return 0;
52 }