Problem Solving using C++

Algorithm Study using C++

字符串匹配算法(3)---String Matching Algorithm

由于有限自动机方法与KMP算法类似,并且有限自动机方法在预处理上的时间复杂度比KMP方法高,所以在本文的讨论中,暂时不讨论有限自动机方法,主要是考虑KMP算法。
KMP算法是一个非常有名的字符串匹配算法,其由Knuth,Morris和Pratt一起提出来的,预处理时间为O(m),其中m为匹配字符串的长度,匹配时间为O(n),其中n为需要匹配的字符串的长度。
核心算法如下:
//预处理部分
int pi[m];
pi[0]=0;
int k = 0;

for(int i=1;i<m;i++)
{
   while((k>0)&&(p[i]!=p[k])
       k=pi[k];

   if(p[i]==p[k])
       k++;

   pi[i]=k;
}

//匹配部分
int k=0;
for(int i=0;i<n;i++)
{
    while((k>0)&&(p[k]!=t[i]))
           k=pi[k];
 
     if(p[k]==t[i])
          k++;

      if(k==m)
       {
            //输出结果,从(i+1-m)开始已经匹配
            k=pi[m-1];//开始下一个匹配
       }
}

具体的可运行的实现代码为:
 1 #include <iostream>
 2 #include <string>
 3 
 4 using namespace std;
 5 
 6 int main(int argc,char* argv[])
 7 {
 8     char *t=NULL,*p=NULL;
 9     int *pi=NULL;
10     string text,pattern;
11 
12     while(1)
13     {
14         cin>>text>>pattern;
15         int n = text.length();        
16         int m = pattern.length();
17 
18         //t= new char[n+1];
19         //p= new char[m+1];
20         t= new char[n];
21         p= new char[m];
22         pi = new int[m];
23 
24         //strcpy(t,text.c_str());
25         //strcpy(p,pattern.c_str());
26         memcpy(t,text.data(),n);
27         memcpy(p,pattern.data(),m);
28 
29         //calculate the PI array
30         int q = 0;
31         pi[0]=0;
32 
33         for(int i=1;i<m;i++)
34         {
35             while((q>0)&&(p[q]!=p[i]))
36             {
37                 q=pi[q];
38             }
39 
40             if(p[q]==p[i])
41                 q++;
42 
43             pi[i]=q;
44         }
45 
46         //use the KMP matching algorithm
47         q = 0;
48         for(int i=0;i<n;i++)
49         {
50             while((q>0)&&(p[q]!=t[i]))
51             {
52                 q = pi[q];
53             }
54 
55             if(p[q]==t[i])
56                 q++;
57 
58             if(q==m)
59             {
60                 cout<<((i+1)-m)<<endl;
61                 q = pi[m-1];
62             }
63         }
64 
65         delete[] t;
66         delete[] p;
67         delete[] pi;
68     }
69 
70     system("pause");
71     return 0;
72 }
73 


posted on 2007-08-21 14:37 Kingoal Lee's Alogrithm Study using cplusplus 阅读(1857) 评论(2)  编辑 收藏 引用

Feedback

# re: 字符串匹配算法(3)---String Matching Algorithm 2007-08-23 11:07 金庆

有错误!测试如下,竟输出2!

abbbababbbbb
ababab
2
  回复  更多评论   

# re: 字符串匹配算法(3)---String Matching Algorithm 2007-08-23 12:42 Kingoal Lee's Alogrithm Study using cplusplus

@金庆
嗯,我刚刚测试了一下,发现上面的出错。
非常感谢你给我指出来!

需要修改的是第52行,将其改为:
q = pi[q-1];
抱歉!  回复  更多评论   



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜