KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。
KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。即确定下一次应该从那个位置重新开始匹配。
char*obj = "cbcba";
char*src = "sdcbcbcba";
要在src中寻找obj，过程如下：
从src第0位开始匹配，s匹配失败，移动1位，
从d开始匹配，d匹配失败，移动1位，
接着从src第2位c开始，匹配，继续b，匹配，继续c，匹配，继续b，匹配，继续c，不匹配，
KMP算法关键点就在这里，要移动最大的距离，在这里是2位，即从src第二位移动到第四位，下次从第四位的c开始匹配。
对于一个要查找的目标字符串，每次在哪一位匹配失败后要移动的最大距离可以提前算出来，存到一个数组里，匹配时直接查找就行。
纯粹自己实现，代码有些丑陋，呵呵
// KMP.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
using namespace std;
int*kk;
int*kkk;
int KMP(char*src, char*obj)
{
int k1 = 0;
int k2 = 0;
int len1 = strlen(src);
int len2 = strlen(obj);
while (k1 < len1)
{
if (src[k1] != obj[0])
{
++k1;
continue;
}
while (k2 < len2+1&&k1+k2 < len1+1)
{
if (k2 == len2)
return k1;
if (src[k1 + k2] == obj[k2])
++k2;
else
if (kkk[k2] == 1)
{
k1 = k1 + kk[k2];
k2 = 0;
continue;
}
else
if (obj[k2 - kk[k2]] == src[k1 + k2])
{
k1 = k1 + kk[k2];
k2 = 0;
continue;
}
else
{
k1 = k1 + k2 + 1;
k2 = 0;
continue;
}
}
}
return -1;
}
int* shift(char*obj)
{
int len = strlen(obj);
kk = new int[len];
kkk = new int[len];
for (int i = 0; i < len; i++)
{
kkk[i ]= 0;
}
kk[0] = 1;
if (len > 1)
{
if (obj[0] == obj[1])
{
kk[1] = 2;
kkk[1] = 1;
}
else
kk[1] = 1;//条件是src与obj第1位匹配的字符等于obj第0个字符，否则kk[1]=2，这由匹配时的src决定
}
int k = 2;
int n = 0;
int m = 1;
while (k < len)
{
bool flag = false;
bool flag1 = false;
while (m<k)
{
if (obj[m] != obj[n])
{
++m;
continue;
}
while (obj[m] == obj[n])
{
flag1 = true;
if (m == k - 1)
{
flag = true;
break;
}
++m;
++n;
}
if (flag)
break;
}
if (!flag1)
if (obj[k] == obj[0])
{
kk[k] = k + 1;//此时直接后移，src无需判断
kkk[k] = 1;
n = 0;
m = 1;
++k;
continue;
}
if (obj[k] == obj[n + 1])
{
kk[k] = k + 1;//此时直接后移，src无需判断
kkk[k] = 1;
n = 0;
m = 1;
++k;
continue;
}
if (flag)
kk[k] = k - 1 - n;//此处假设src与obj第k位匹配的字符等于obj第n+1个字符，否则kk[k]=k+1，kmp匹配时需做判断
else
kk[k] = k;//此处假设src与obj第k位匹配的字符等于obj第0个字符，否则kk[k]=k+1，kmp匹配时需做判断
n = 0;
m = 1;
++k;
}
return kk;
}
int _tmain(int argc, _TCHAR* argv[])
{
//char*obj = "cbcba";
//char*src = "sdcbcbcba";
//char*src = "abacaabacabacabaabb";
//char*obj = "abacab";
char*src = "BBC ABCDAB ABCDABCDABDE";
char*obj = "ABCDABD";
int len = strlen(obj);
shift(obj);
for (int i = 0; i < len; i++)
cout << kk[i] << endl;
cout << endl;
for (int i = 0; i < len; i++)
cout << kkk[i] << endl;
cout << KMP(src, obj) << endl;
system("pause");
return 0;
}