KMP算法_模板

KMP算法_模板_C++

　　这个博客讲得非常优秀，可惜它是Java版本的

　　http://blog.csdn.net/yutianzuijin/article/details/11954939/

　　a 为匹配串，b 为目标串

　　通俗讲就是在 a 中找 b

　　时间复杂度 O(a.len+b.len)

 1 void init()
 2 {
 3     int i,j=0;
 4     for (i=1;i<lb;i++)
 5         {
 6             while (j&&b[i]!=b[j]) j=next[j];
 7             if (b[i]==b[j]) j++;
 8             next[i+1]=j;
 9         }
10 }
11 void kmp()
12 {
13     int i,j=0;
14     for (i=0;i<la;i++)
15         {
16             while (j&&a[i]!=b[j]) j=next[j];
17             if (a[i]==b[j]) j++;
18             if (j==lb)
19                 {
20                     printf("%d ",i-j+1);
21                     j=next[j];
22                 }
23         }
24 }

在此获取联系方式：http://www.cnblogs.com/hadilo/p/5932395.html