KMP总结

首先给一个我能看懂的KMP讲解：

http://blog.csdn.net/v_july_v/article/details/7041827 来自大神july

文章很长，但是慢慢看，会发现讲的很好。

首先有两种KMP的写法：

第一种：

 1 void getNext()
 2 {
 3     int i=0;
 4     int j=-1;
 5     nexts[0]=-1;
 6     while(i<m)
 7     {
 8         if(j==-1||num2[i]==num2[j])
 9         {
10             i++;
11             j++;
12             nexts[i]=j;
13         }
14         else
15             j=nexts[j];
16     }
17     return;
18 }
19 int Kmp()
20 {
21     int i=0;
22     int k=0;
23     while(i<n&&k<m)
24     {
25         if(k==-1||num1[i]==num2[k])
26         {
27             i++;
28             k++;
29         }
30         else
31             k=nexts[k];
32         if(k==m)
33             return i-m+1;
34     }
35    /* if(i<n)
36         return i-m+1;
37     else*/
38         return -1;
39 }

View Code

第二种：

 1 void getNext()
 2 {
 3     int i=0;
 4     int j=-1;
 5     nexts[0]=-1;
 6     while(i<m)
 7     {
 8         if(j==-1||s2[i]==s2[j])
 9         {
10             i++;
11             j++;
12             nexts[i]=j;
13         }
14         else
15             j=nexts[j];
16     }
17     return;
18 }
19 int Kmp()
20 {
21     int i=0;
22     int k=0;
23     int cnt=0;
24     for(int i=0;i<n;i++)
25     {
26         while(k&&s1[i]!=s2[k])
27             k=nexts[k];
28         if(s1[i]==s2[k])
29             k++;
30         if(k==m)
31             cnt++;
32     }
33    return cnt;
34 }

View Code

这两种写法用于不同的地方。

题目总结：

1.求匹配串在文本串出现的次数

直接利用第二种写法即可。

题目：HDU - 1686

2.求匹配串在文本串第一次匹配成功时的起始位置。

套用第一种写法即可。

题目：HDU - 1711

3.给定一个字符串，问我们还需要添加几个字符可以构成一个由n个循环节组成的字符串。

利用Next数组的性质，

假设字符串的长度为len，那么最小的循环节就是cir = len-next[len] ;
如果有len%cir == 0,那么这个字符串就是已经是完美的字符串，不用添加任何字符；
如果不是完美的那么需要添加的字符数就是cir - (len-(len/cir)*cir))，相当与需要在最后一个循环节上面添加几个。

题目：HDU - 3746

4.给你一个字符串 s 求出所有满足s[i] == s[i+p] ( 0 < i+p < len )的 p ;

来自于其他人的做饭：

•知识点：KMP算法、对next数组的理解

•KMP算法中next数组的含义是什么？

•next数组：失配指针

•如果目标串的当前字符i在匹配到模式串的第j个字符时失配，那么我们可以让i试着去匹配next(j)

•对于模式串str，next数组的意义就是：

•如果next(j)=t,那么str[1…t]=str[len-t+1…len]

•我们考虑next(len)，令t=next(len);

•next(len)有什么含义？

•str[1…t]=str[len-t+1…len]

•那么，长度为len-next(len)的前缀显然是符合题意的。

•接下来我们应该去考虑谁？

•t=next( next(len) );

•t=next( next (next(len) ) );

• 一直下去直到t=0,每个符合题意的前缀长是len-t

题目：FZU - 1901

KMP总结

推荐阅读