关于KMP算法的感想

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

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

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

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 #define MAXS 5000
 6 #define MAXT 500
 7 
 8 char S[MAXS];
 9 char T[MAXT];
10 int next[MAXT];
11 
12 // 关键在于next数组的推导，next[i] 代表的意义是:如果朴素匹配失配，j 应该变为多少
13 //在推导next时，使用了已经推导了的next数组，所以我感觉有dp的思想在里面
14 void get_next(char * t,int l)   //没优化但不易出错，其实不优化不会慢多少
15 {
16     int i=0,j=-1;
17     next[0]=-1;
18     while(i<l)
19     {
20         if (j==-1||T[i]==T[j])
21             next[++i]=++j;
22         else
23             j=next[j];  //回溯
24     }
25 }
26 
27 /*
28 //优化的next很有意思，将重复的状态叠在一起了
29 void get_next(char * t,int l)   //优化的，一定注意，要慎重使用
30 {
31     int i=0,j=-1;
32     next[0]=-1;
33     while (i<l)
34     {
35         if (j==-1||T[i]==T[j])
36         {
37             i++;j++;
38             if (T[i]!=T[j]) next[i]=j;
39             else next[i]=next[j];
40         }
41         else j = next[j];
42     }
43 }
44 */
45 
46 int KMP(char *s,char *t)    //求匹配索引
47 {
48     int lens = strlen(s);
49     int lent = strlen(t);
50     get_next(t,lent);
51     int i=-1,j=-1;
52     while (i<lens&&j<lent)
53     {
54         if (j==-1||S[i]==T[j])
55             i++,j++;
56         else
57             j = next[j];
58 
59     }
60     if (j==lent)
61         return i-lent;
62     return -1;
63 }
64 
65 int KMP_count(char *s,char *t) //求匹配数,一定要用没优化的
66 {
67     int res = 0;
68     int lens = strlen(s);
69     int lent = strlen(t);
70     get_next(t,lent);
71     int i=-1,j=-1;
72     while (i<lens)
73     {
74         if (j==-1||S[i]==T[j])
75             i++,j++;
76         else
77             j = next[j];
78         if (j==lent)
79         {
80             res++;
81             j = next[j];
82         }
83     }
84     return res;
85 }
86 
87 int main()
88 {
89     scanf("%s",S);
90     scanf("%s",T);
91     int p = KMP(S,T);
92     printf("%d
",p);
93     return 0;
94 }

View Code