KMP算法原理
现在假设有两个字符串A:bbc abcdab abcdabde，B：abcdabd。现在要在A中找B。比较暴力的方法是直接搜索：
void gosearch()
{
int la=strlen(a),lb=strlen(b);
for(int i=0;i<la;i++)
{
int j=0;
while(j<lb&&a[i+j]==b[j])j++;
if(j==lb)printf("%d\n",i+j);
}
}可以发现当匹配到如图所示：
当匹配到D时匹配失败，那么上面程序的做法是i+1，然后继续匹配。考虑到我们中间的ABCDAB都已经匹配过了，如果我们知道第5，6个字母AB与第1，2个字母相同，那么最佳的做法应该是直接将B字符串移至如图：
实际上第5，6个字母AB，是B串子串的一个后缀，第1，2个字符是B串子串的一个前缀。KMP算法的核心思想就是用被匹配的字符串子串的最长公共前缀和后缀得到一个跳转表next[]，从而实现匹配时的快速跳转。B串next[]数组：
next[]数组代码实现
void makenext()
{
int j=0;
int lb=strlen(b);
for(int i=1;i<lb;i++)
{
while(j>0&&b[i]!=b[j])j=next1[j];//核心
if(b[i]==b[j])j++;
next1[i+1]=j;
}
}
上述代码最核心就是while循环，举两个例子说明其作用：
还是选取B串作为说明。
假设现在要求next[6]，那么当前的j=next[5]=1（next数组的下标从1开始），那么b[5]=b[1]，j++，next[6]=2.
意思是第5个字符A已经匹配了第一个字符A，第6个字符B也匹配了第二个字符B，next[6]=next[5]+1。
然后求next[7]，当前j=2。但是b[6]!=b[2]，那么跳转到以b[2]为后缀的前一个字符继续匹配。
搜索匹配
搜索匹配的过程和next[]数组的求取很类似，代码：
void gosearch()
{
int j=0;
int la=strlen(a),lb=strlen(b);
for(int i=0;i<la;i++)
{
while(j>0&&a[i]!=b[j])j=next1[j];
if(a[i]==b[j])j++;
if(j==lb)
{
printf("%d",i-j);
}
}
}
完整代码样例
#include<stdio.h>
#include<string>
#include<string.h>
using namespace std;
int next1[100];
char a[300];
char b[100];
void makenext()
{
int j=0;
int lb=strlen(b);
for(int i=1;i<lb;i++)
{
while(j>0&&b[i]!=b[j])j=next1[j];
if(b[i]==b[j])j++;
next1[i+1]=j;
}
}
void gosearch()
{
int j=0;
int la=strlen(a),lb=strlen(b);
for(int i=0;i<la;i++)
{
while(j>0&&a[i]!=b[j])j=next1[j];
if(a[i]==b[j])j++;
if(j==lb)
{
printf("%d",i-j);
}
}
}
int main()
{
scanf("%s%s",a,b);
makenext();
gosearch();
return 0;
}
这篇文章借鉴了两位大神的博客，包括图片也出自这两篇博客：
http://blog.csdn.net/yutianzuijin/article/details/11954939/
http://www.cnblogs.com/c-cloud/p/3224788.html
