传统的字符串匹配算法中，为了在一段字符串中查找模式字符串的话需要使用2个循环嵌套起来，例如：
int i=0;
while(i< str.length()-parten.length())
{
int j=0;
while(parten[j]==str[i])
{
++i;
++j;
}
if(j==parten.length())
return true;
i=i-j+1;
}
return false;
这种方法很黄很暴力，其中对于第一个循环，会产生回溯。也就是说如果一个字符串：
bacbababaabcba来匹配模式字符串abababa。当原字符串的a和模式字符串的c做比较的时候，
|
b
|
a
|
c
|
b
|
a
|
b
|
a
|
b
|
a
|
a
(i=9)
|
b
|
c
|
b
|
a
|
|
|
|
|
|
a
|
b
|
a
|
b
|
a
|
b
(j=5)
|
a
|
|
|
|
当发现不匹配的时候i会往前递进一位，此时从原字符串的第i+1位开始匹配字符串：
|
b
|
a
|
c
|
b
|
a
|
b
(i=5)
|
a
|
b
|
a
|
a
|
b
|
c
|
b
|
a
|
|
|
|
|
|
|
a
(j=0)
|
b
|
a
|
b
|
a
|
b
|
a
|
|
|
Kmp算法就是为了让i不再回溯而提出的一种算法。在kmp算法中
当匹配失败后，i维持原来的值不变，只需要变动j值即可。我们可以把j值直接加上一个位移忽略掉那些肯定会匹配失败
的可能，现在的问题是如何求这个位移？
以模式字符串“abababa”为例子，位于字符串第3个位置的字母‘b’和要匹配的字符串T[0..k]做匹配运算的时候，假如
匹配失败，我们要寻求一个位移，目前我们所知道的条件有：
1、目前的情况下，j指向字符‘b’的位置，也就是3。
2、模式的前3个字符‘a’‘b’‘a’都匹配成功了，也就是说T[i-1]=‘a’；T[i-2]=‘b’；T[i-3]=‘a’。
3、匹配肯定是从i-3的位置开始的。
如果用最暴力的方法，那么把j从新置为0。但是我们注意到j=1的位置的字符和j=3的位置的字符是相同的。也就是说可以
直接从j=1重新开始比较而不是j=0。
通过总结归纳，可以得出：对于模式字符串中的每个字符计算出来的位移就是匹配模式字符串前缀的最长后缀的长度减一
（由于这里采用下标从0计数的方法，所以还要减去1）。
匹配字符串前缀的最长后缀的长度减一。
匹配字符串前缀的最长后缀的长度减一。
这就是KMP算法唯一的奥秘了。
接下来，我们就可以不用考虑带匹配的字符串的内容，只需要根据模式字符串本身就可以求出每个字符如果匹配失败后需
要位移的距离。计算完成后我们就可以得到一个整型的数组，数组的长度就是模式字符串的长度，数组中的每个元素就是每个
移动到距离。
为了对模式字符串的每个字符求解移动的距离，可以使用暴力的方法用2个循环的方法求得。仔细一看这又是一个字符串
匹配的方法，只不过匹配对象不一样了。
这里先别急着求解移动的距离，让我们先假设我们计算出了每个字符要移动的距离的数组next[]，如何来进行字符匹配。
int i=0;
int j=0;
while(i< str.length()-parten.length())
{
while(j==0 || parten[j]==str[i])
{
++i;
++j;
}
if(j==parten.length())
return true;
j=next[j]; //next[]就是计算出来的要移动距离
}
和前文的程序相比改动灰常灰常的小。再也不需要去改变i的值，当匹配不成功的时候只需要去取出预计算的next[]的值即可。
让我们回到计算next[]的问题上来。根据前面得出的结论，我们需要找出匹配字符串前缀的最长后缀即可。考察字符串
“aba”，前缀可以是“a”、“ab”。后缀可以是“ba”、“a”。所以对于字符串“aba”的最后一个字母“a”它的next值
就是0。
再考察字符串“ababa”，前缀可以是“a”、“ab”、“aba”、“abab”。后缀可以是“baba”、“aba”、“ba”、
“a”。所以这里匹配的最长后缀是“aba”所以这个next值等于“aba”的长度减一等于2。
如果使用暴力的方法列举每一个前缀和后缀比较的话，还是会遇到回溯的老问题。对于比较短的模式字符串的话效率尚
可，如果模式字符串的长度比较长的话就不太妙了。
在前面KMP的匹配算法中，由于我们知道了一个next[]数组，就正好知道了j跳转的值，这里我们同样可以使用这个方法。
假设在计算每个字符的next值的时候我们也使用2个循环，并且使用i控制下图中上面的字符串的比较位置，用j控制下图中下
面字符串的比较位置。
因为我们需要找出匹配前缀的最大的后缀的长度，而对于一个字符串来说前缀和后缀的匹配至少需要相隔一个字符，如下
图所示：
|
a
|
b (i=1)
|
a
|
b
|
|
|
|
|
|
|
a (j=0)
|
b
|
a
|
b
|
|
|
|
当我们要找出字符串“abab”的最后一个字母‘b’的next值，那么就如同上图一样错开一位，如果不匹配，就把下面一
行的字符串向右再移动一位：
|
a
|
b
|
a
|
b (i=3)
|
|
|
|
|
|
|
|
a
|
b (j=1)
|
a
|
b
|
|
|
这样就正好匹配，得出next[3]=1。当需要找出字符串“ababb”的最后一个字符next值的时候，是如下图所示的场景：
|
a
|
b
|
a
|
b
|
b (i=4)
|
|
|
|
|
|
|
a
|
b
|
a (j=2)
|
b
|
a
|
|
发现不匹配，此时我们知道上一次匹配是成功的，所以可以让j直接从上一次匹配成功的位置j=1。
|
a
|
b
|
a
|
b
|
b (i=4)
|
|
|
|
|
|
|
|
a
|
b (j=1)
|
a
|
b
|
a
|
这样刚好得到匹配的后缀。得出next。
于是可以得出求得next[]的算法：
while (i<len)
{
while (j<0 || (i<len && B[i]==B[j]))
{
++i;
++j;
next[i]=j;
}
j=next[j];
}
我们注意到，这次比较还是c和a比较，而这次比较在上一次就已经比较过了。所以为了避免这个比较，只需要把next的位于4的位置的值直接设置为next位于2的位置的值即可。那么计算next数组的算法如下：
while (i<len)
{
while (j<0 || (i<len && B[i]==B[j]))
{
++i;
++j;
If(B[i]==B[j])
next[i]=next[j];
else
next[i]=j;
}
j=next[j];
}
到此，又把数据结构课本上的内容啰唆了一次。
最后是完整的代码，为了调试方便，加入了不少语句使得算法臃肿了不少。
#define INIT_POSISION 0
int KMP(const char* text,const char* parten_text)
{
unsigned int parten_len=strlen(parten_text);
unsigned int text_len=strlen(text);
int* nextArray=new int[parten_len];
findNext2(parten_text,nextArray);
int text_iterator=0;
int parten_iterator=0;
while (text_iterator<=text_len-parten_len) //如果剩下的字符长度小于模式的长度，就不用匹配了
{
char char_str=text[text_iterator];
char char_parten=parten_text[parten_iterator];
while (parten_iterator<=INIT_POSISION || (parten_iterator<parten_len &&
char_str==char_parten))
{
++text_iterator;
++parten_iterator;
char_str=text[text_iterator];
char_parten=parten_text[parten_iterator];
}
if (parten_iterator==parten_len) //完全匹配
{
return text_iterator-parten_len-1; //返回本次匹配的首字符位置
}
//没有完全匹配，从next数组取下一个位置重新匹配
parten_iterator=nextArray[parten_iterator];
}
return INIT_POSISION;
}
void findNext2(const char* B,int* next)
{
int len=strlen(B);
next[ 0 ] = next[ 1 ] = -1 ;
int j=-1;
int i=0;
while (i<len)
{
while (j<0 || (i<len && B[i]==B[j]))
{
++i;
++j;
next[i]=j;
}
j=next[j];
}
for (int i=0;i<len;++i)
{
cout<<next[i]<<endl;
}
}