bon

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

重新看了KMP算法,有了新的理解。主要参考资料/Files/bon/kmp2.pdf

附件里说得很好,跟传统的教程不同。
首先定义串s的前缀s',空串也是s的前缀,还有一个定义叫做proper prefix:s'是s的proper prefix等价于s'是s的prefix且s' != s,这个定义对于理解KMP有着关键的作用。同样可以定义对应的后缀以及proper suffix。

下面假设模式串为s,被匹配的串为t,且第0个字符是串的第一个字符。

KMP的精髓在于计算next数组(附件里为pi数组)。next[i]=k,k<i(注意这里不取等号,想想为什么),s[0...k]是s的proper prefix,也是s[0...i]的proper suffix,且k是最大的(即不存在l>k,s[0...l]是s[0...i]的proper prefix且是s[0...i]的proper suffix)。

那么next[0]=-1就很自然地被理解:表示的是空串是s[0...0]的proper prefix且是s[0...0]的proper suffix。
另外k严格小于i也可以理解:若k==i,但s[0...i]不是s[0...i]的proper prefix 也不是proper suffix,这跟定义冲突。

上述可以用下图来说明。


上面的式子定义了next数组,但还没有指出怎么计算next。假设next[0...i]已经计算出来了,next[i+1]怎么算。
这里用的是动态规划的思想。设s[0...k+1]是s[0...i+1]最长的proper prefix且是proper suffix,k<i,则明显地s[0...k+1]符合以下性质:

1. s[0...k]是s[0...i]的proper prefix (这一点很明显,由于k<i)
2. 且s[0...k]是s[0...i]的proper suffix (若不然,s[0...k+1]肯定无法组成s[0...i+1]的suffix)
3. 且s[k+1]==s[i+1]。

因此我们的任务就是找到这样一个k。而s[0...k]是s[0...i]的proper prefix 和proper suffix这个性质使得我们可以利用已计算的next[0...i]来找k。

找的过程实质就是找到s[0...i+1]一个最长的proper prefix s[0...k], 这个prefix 同时是s[0...i+1]的proper suffix且有s[i+1]==s[k+1],见下图:

假设s[0...kx]都是s[0...i+1]的proper prefix,且都是s[0...i]的proper suffix。设s[k1+1] != s[i+1],则s[0...k1+1]不可能是s[0...i+1]的proper suffix。
设s[k2+1] = = s[k3+1] = = s[i+1],但由于k3>k2,所以next[i+1] = k3+1

下面看poj上的一道题目的代码:
 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 char w[10001],t[1000001];
 6 int n;
 7 int next[10001];
 8 
 9 int main()
10 {
11     scanf("%d",&n);
12     while(n--){
13         scanf("%s",w);
14         scanf("%s",t);
15         // process w
16         int wLength = strlen(w);
17         next[0]=-1;
18         int i=1;
19         int p;
20         while(i<wLength){
21             p=next[i-1];
22             while(p!=-1 && w[p+1]!=w[i]) p=next[p];
23             if(w[p+1]==w[i]) next[i]=p+1;
24             else next[i]=-1;
25             i++;
26         }
27         //for(i=0;i<wLength;i++) printf("%d",next[i]);
28         //printf("\n");
29         // matching
30         int j=-1,cnt=0;
31         i=-1;
32         int tLength = strlen(t);
33         while(j<tLength){
34             if(t[j+1]==w[i+1]){
35                 i++;
36                 j++;
37                 if(i==wLength-1){
38                     cnt++;
39                     i=next[i];
40                 }
41             }else{
42                 if(i==-1) j++;
43                 else i=next[i];
44             }
45         }
46         printf("%d\n",cnt);
47     }
48     return 1;
49 }
50 


posted on 2008-07-25 11:45 bon 阅读(251) 评论(0)  编辑 收藏 引用 所属分类: Programming Contest

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Google PageRank 
Checker - Page Rank Calculator