关于KMP算法的感想

今天，看了KMP,首先是在网上看的，看了很久没看懂，有很多思想，很多next的推导，就相当于很多的版本，后来，去看了<<大话数据结构>>这本书，才看懂，这KMP的神奇之处，这本书写得很详细，非常好理解，对于KMP的思想，对于next的推导，next的优化，都说得比较好理解。看懂后，才惊觉，网上的很多人竟然是不懂KMP就敢写，很容易误导人，比如有的对于next的推导过程，根本就不是O(m)，应该算是O(m*m)的，唉。。。看完next的推导，优化，不觉惊叹这牛逼的算法啊。其实我想说，想要看KMP,最好去看书，网上学真难。。。下面给出KMP的模板吧，也写了一点注释，要讲解KMP我也是没这么多时间，也很难讲通

对于字符串，有个 \0 结尾的特性。

KMP 测试题 http://www.cnblogs.com/haoabcd2010/p/6842448.html

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 using namespace std;

 #define MAXS 5000

 #define MAXT 500

 char S[MAXS];

 char T[MAXT];

 int next[MAXT];

 // 关键在于next数组的推导，next[i] 代表的意义是:如果朴素匹配失配，j 应该变为多少

 //在推导next时，使用了已经推导了的next数组，所以我感觉有dp的思想在里面

 void get_next(char * t,int l)   //没优化但不易出错，其实不优化不会慢多少

 {

     int i=,j=-;

     next[]=-;

     while(i<l)

     {

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

             next[++i]=++j;

         else

             j=next[j];  //回溯

     }

 }

 /*

 //优化的next很有意思，将重复的状态叠在一起了

 void get_next(char * t,int l)   //优化的，一定注意，要慎重使用

 {

     int i=0,j=-1;

     next[0]=-1;

     while (i<l)

     {

         if (j==-1||T[i]==T[j])

         {

             i++;j++;

             if (T[i]!=T[j]) next[i]=j;

             else next[i]=next[j];

         }

         else j = next[j];

     }

 }

 */

 int KMP(char *s,char *t)    //求匹配索引

 {

     int lens = strlen(s);

     int lent = strlen(t);

     get_next(t,lent);

     int i=-,j=-;

     while (i<lens&&j<lent)

     {

         if (j==-||S[i]==T[j])

             i++,j++;

         else

             j = next[j];

     }

     if (j==lent)

         return i-lent;

     return -;

 }

 int KMP_count(char *s,char *t) //求匹配数,一定要用没优化的

 {

     int res = ;

     int lens = strlen(s);

     int lent = strlen(t);

     get_next(t,lent);

     int i=-,j=-;

     while (i<lens)

     {

         if (j==-||S[i]==T[j])

             i++,j++;

         else

             j = next[j];

         if (j==lent)

         {

             res++;

             j = next[j];

         }

     }

     return res;

 }

 int main()

 {

     scanf("%s",S);

     scanf("%s",T);

     int p = KMP(S,T);

     printf("%d\n",p);

     return ;

 }

巴特西

关于KMP算法的感想

最新文章

热门文章