poj3461 KMP 小结

这两天简单研究了KMP ，网上有很多讲解的文章，我在这里就不班门弄斧啦。大家要是学的话，可以看看这个人写的http://www.matrix67.com/blog/archives/115 。KMP要是只看讲解，估计会很困难，大家可以结合具体例子去调试分析学习，比较快把。NEXT 有很多不同的版本，我喜欢传统的版本，下面就用POJ这个题做个模板把。
3561这个题目说的长。一看例子就知道，和那个剪画布的一模一样。就是从第二个里面找第一个串的数量。当然这里主串交长，简单的BF是行不通的。下面代码

 1 #include<stdio.h>
 2 #include<string.h>
 3 char a[10001],s[1000101];
 4 int next[10001],len1,len2;
 5 void NEXT()
 6 {
 7 
 8     int j,k;
 9     next[0]=-1;
10     j=0;
11     k=-1;
12     while(j<len1)
13     {
14         if(k==-1||a[k]==a[j])
15         {
16             k++;
17             j++;
18             next[j]=k;
19         }
20         else
21             k=next[k];
22     }
23 }
24 int KMP()
25 {
26     int j=0,i=0,sum=0;
27     NEXT();
28     while(i<len2)
29     {
30         if(j==-1||a[j]==s[i])
31         {
32             i++;
33             j++;
34         }
35         else
36             j=next[j];
37         if(j==len1)////模串到头说明匹配成功
38             sum++;
39     }
40     return sum;
41 }
42 int main()
43 {
44     int sum,T;
45     scanf("%d",&T);
46     while(T--)
47     {
48         scanf("%s%s",a,s);
49         len1=strlen(a);
50         len2=strlen(s);
51         sum=0;
52         sum=KMP();
53         printf("%d\n",sum);
54     }
55     return 0;
56 }

第一次在博客园上写，有点生疏，以前一直在新浪上，但是代码太乱，也不想换窝，今天痛下决心换啦！