KMP算法
与BF算法相比，KMP的改进之处在于，当主串当前指针（下标）字符与模式串当前指针（下标）字符不相等时，主串的指针i不需要回溯，而是利用已经得到的"部分匹配"的结果，将模式串尽量的右移，继续进行匹配！
注：统一，本篇讨论的字符串的下标都是从0开始的
例如：
主串的
i指针无需回溯到7，而是保持不动，此时i = 12与j = 6不匹配，利用已"部分匹配"的模式串部分 ABCDAB 将整个模式串尽量右移。可以发现已部分匹配的模式串部分
ABCDAB 最长公共前后缀为AB，右移的最大距离即前缀部分与后缀部分重叠
可见此时
j（下标值）即为之前j = 6时，其前面部分匹配串的最长公共前后缀；用
Next数组保存当前字符前的部分串（不包含当前字符）的最长公共前后缀的大小如上栗中，
next[6] = 2
Next数组
注：如何理解 j = 0 时，next[0] = -1?
失配于模式串首字符流程
KMP算法Code框架 ： 按以上定义实现（Next[]构建下面分析）
/*
@ Author : z
@ Date : 2018.7.30
@ Title : KMP
@ In : str 主串
substr 模式串
@ Out :
*/
#include <string>
int KMP(string str, string substr)
{
1. 创建模式串substr的next[ ] 数组
int * next = BuildNext(substr);
int str_len = str.length();
int substr_len = substr.length();
int i = 0; //主串下标指针
int j = 0; //模式串下标指针
while (i < str_len && j < substr_len)
{
if ( (0 > j) || ( str[i] == substr[j]) )
{ 通配符匹配或字符匹配
i ++；
j ++; // 携手共进
}
else
{ 失配，模式串尽量右移，即指针 j 左移 = next[j] ， i 不变
j = next[j];
}
}// end_while
delete []next; //释放next[]数组
return i-j; // >= 0，匹配成功，且返回主串中模式串位置
// < 0 , 匹配失败
}
Key：关键在于模式串next[]数组的构建，下面介绍！！！
根据上面 Next数组 的定义实现 next[ ]表的构造
利用递推来构造 next[ ]表，以下：
已知
next[ j ]的值，如何高效计算next[ j + 1 ]注 : 严格按定义，肯定能实现，重点在于理解！
next[ ]构建Code
@ Author : zzz
@ Date : 2018.7.30
@ Title : Build next
@ In : str 字符串
@ Out :
#include <string>
int * BuildNext(string str)
{
int len = str.length();
int j = 0; // "主"串指针
int * Next = new int[len]; // Next[] 表
/************************************************************/
# 初始化 Next[0] = -1,
# str[-1]作为通配符，此处 t 可视为记录：最大公共前后缀的长度
/************************************************************/
int t = Next[0] = -1;
while ( j < len-1)
{
if ((0 > t) || (str[j] == str[t]))
{//哨兵匹配 即 t = -1 或 字符匹配
Next[++j] = ++t;
}
else
{//失配 , 递推！！！
t = Next[t] ;
}
}
return Next;
}
分析上面代码中循环中的 if 和 else
if ((0 > t) || (str[j] == str[t]))是分析中的情况1,next[j+1] = next[j] + 1，next[j]用 t 记录else : t = Next[t]
举个栗子，展示Next[]数组的构建过程
依此类推
else的递推过程
KMP - Next[ ] 数组的优化
反例
改进 Next[ ] Code
@ Author : zzz
@ Date : 2018.7.30
@ Title : 改进Next
@ In : str字符串
@ Out :
#include <string>
int * BuildNext(string str)
{
int len = str.length();
int j = 0; // "主"串指针
int * Next = new int[len]; // Next[] 表
/************************************************************/
# 初始化 Next[0] = -1,
# str[-1]作为通配符，此处 t 可视为记录：最大公共前后缀的长度
# t 也可视为模式串指针，大小为最大公共前后缀的长度
/************************************************************/
int t = Next[0] = -1;
while ( j < len-1)
{
if ((0 > t) || (str[j] == str[t]))
{// 匹配 ， 改进处！！！
j ++;
t ++;
Next[j] = ( str[j] != str[t] ? t : Next[t] ); // !!! !!!
}
else
{//失配
t = Next[t] ;
}
}
return Next;
}
改进Next数组构建，递推的过程！
