KMP总结

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

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

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

首先有两种KMP的写法：

第一种：

 void getNext()

 {

     int i=;

     int j=-;

     nexts[]=-;

     while(i<m)

     {

         if(j==-||num2[i]==num2[j])

         {

             i++;

             j++;

             nexts[i]=j;

         }

         else

             j=nexts[j];

     }

     return;

 }

 int Kmp()

 {

     int i=;

     int k=;

     while(i<n&&k<m)

     {

         if(k==-||num1[i]==num2[k])

         {

             i++;

             k++;

         }

         else

             k=nexts[k];

         if(k==m)

             return i-m+;

     }

    /* if(i<n)

         return i-m+1;

     else*/

         return -;

 }

第二种：

 void getNext()

 {

     int i=;

     int j=-;

     nexts[]=-;

     while(i<m)

     {

         if(j==-||s2[i]==s2[j])

         {

             i++;

             j++;

             nexts[i]=j;

         }

         else

             j=nexts[j];

     }

     return;

 }

 int Kmp()

 {

     int i=;

     int k=;

     int cnt=;

     for(int i=;i<n;i++)

     {

         while(k&&s1[i]!=s2[k])

             k=nexts[k];

         if(s1[i]==s2[k])

             k++;

         if(k==m)

             cnt++;

     }

    return cnt;

 }

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

题目总结：

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总结

最新文章

热门文章