kmp算法c++代码实现

浏览数：19 / 时间：2015年06月08日 
 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 }

 

由于前面已经讲明白了kmp算法的原理，下面我仅仅贴出代码：

 

kmp算法c++代码实现,古老的榕树,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢