我们这里说的KMP不是拿来放电影的（虽然我很喜欢这个软件），而是一种算法。KMP算法是拿来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字符串A="I'm matrix67"，字符串B="matrix"，我们就说B是A的子串。你可以委婉地问你的MM：“假如你要向你喜欢的人表白的话，我的名字是你的告白语中的子串吗？”
解决这类问题，通常我们的方法是枚举从A串的什么位置起开始与B匹配，然后验证是否匹配。假如A串长度为n，B串长度为m，那么这种方法的复杂度是O (mn)的。虽然很多时候复杂度达不到mn（验证时只看头一两个字母就发现不匹配了），但我们有许多“最坏情况”，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我们将介绍的是一种最坏情况下O(n)的算法（这里假设 m<=n），即传说中的KMP算法。
这种改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特-莫里斯-普拉特算法（简称为KMP算法）。该算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的‘部分匹配’的结果将模式向右‘滑动’尽可能远的一段距离后，继续进行比较。
KMP算法是一种用于字符串匹配的算法,这个算法的高效之处在于当在某个位置匹配不成功的时候可以根据之前的匹配结果从模式字符串的另一个位置开始,而不必从头开始匹配字符串.
因此这个算法的关键在于,当某个位置的匹配不成功的时候,应该从模式字符串的哪一个位置开始新的比较.假设这个值存放在一个next数组中,其中next数组中的元素满足这个条件:next[j] = k,表示的是当模式字符串中的第j + 1个(这里是遵守标准C语言中数组元素从0开始的约定,以下不再说明)发生匹配不成功的情况时,应该从模式字符串的第k + 1个字符开始新的匹配.如果已经得到了模式字符串的next数组,那么KMP算法的实现如下C# 代码:FindBytesKMP
#region #FindBytesKMP
/// <summary>
/// 求一个字符串的回溯函数。
/// 约定序列下标从0开始。
/// 回溯函数是整数集[0,n-1]到N的映射，n为字符串的长度。
/// 回溯函数的定义：
/// 设存在非空序列L，i为其合法下标；
/// L的前置序列集为：{空集,L中所有以i-1为最后一个元素下标的子序列}
/// L的前置序列集为：{空集,L中所有以0为第一个元素下标的子序列}
/// 下标i的回溯函数值的定义为：
/// 如果i=0,回溯函数值为-1
/// 否则i的回溯函数值为i的前置序列集和L的前置序列集中相等元素的最大长度,但是相等的两个元素不能是L中的同一个子串，例如[0-i,1]~reversed
/// 换句话说是，设集合V={x,x属于i的前置序列集,并且x属于L的前置序列集，并且x的长度小于i}，回溯函数值为max(V).length
/// 当i=0时并不存在这样的一个x，所以约定此时的回溯函数值为-1
/// 回溯函数的意义：
/// 如果子串中标号为j的字符同主串失配，那么将子串回溯到next[j]继续与主串匹配，如果next[j]=-1,则主串的匹配点后移一位，同子串的第一个元素开始匹配。
/// 同一般的模式匹配算法相比，kmp通过回溯函数在失配的情况下跳过了若干轮匹配(向右滑动距离可能大于1)
/// kmp算法保证跳过去的这些轮匹配一定是失配的，这一点可以证明
/// </summary>
/// <param name="pattern">模式串，上面的注释里将其称为子串</param>
/// <returns>回溯函数是 kmp 算法的核心，本 函数 依 照其定义求出回溯函数，KMP函数依照其意义使用回溯函数。</returns>
private int[] FindBytesNext(byte[] pattern)
{
int[] next = new int[pattern.Length];
next[0] = -1;
if (pattern.Length < 2) //如果只有1个元素不用kmp效率会好一些
{
return next;
}
next[1] = 0; //第二个元素的回溯函数值必然是0，可以证明：
//1的前置序列集为{空集,L[0]}，L[0]的长度不小于1，所以淘汰，空集的长度为0，故回溯函数值为0
int i = 2; //正被计算next值的字符的索引
int j = 0; //计算next值所需要的中间变量，每一轮迭代初始时j总为next
while (i < pattern.Length) //很明显当i==pattern.Length时所有字符的next值都已计算完毕，任务已经完成
{ //状态点
if (pattern == pattern[j]) //首先必须记住在本函数实现中，迭代计算next值是从第三个元素开始的
{ //如果L等于L[j]，那么next = j + 1
next = ++j;
}
else
{ //如果不相等则检查next的下一个可能值----next[j]
j = next[j];
if (j == -1) //如果j == -1则表示next的值是1
{ //可以把这一部分提取出来与外层判断合并
//书上的kmp代码很难理解的一个原因就是已经被优化，从而遮蔽了其实际逻辑
next = ++j;
}
}
}
return next;
}
/// <summary>
/// KMP函数同普通的模式匹配函数的差别在于使用了next函数来使模式串一次向右滑动多位称为可能
/// next函数的本质是提取重复的计算
/// </summary>
/// <param name="source">主串</param>
/// <param name="pattern">用于查找主串中一个位置的模式串</param>
/// <returns>-1表示没有匹配，否则返回匹配的标号</returns>
public int FindBytesKMP(byte[] source, byte[] pattern)
{
int[] next = FindBytesNext(pattern);
int i = 0; //主串指针
int j = 0; //模式串指针
//如果子串没有匹配完毕并且主串没有搜索完成
while (j < pattern.Length && i < source.Length)
{
if (source == pattern[j]) //i和j的逻辑意义体现于此，用于指示本轮迭代中要判断是否相等的主串字符和模式串字符
{
i++;
j++;
}
else
{
j = next[j]; //依照指示迭代回溯
if (j == -1) //回溯有情况，这是第二种
{
i++;
j++;
}
}
}
//如果j==pattern.Length则表示循环的退出是由于子串已经匹配完毕而不是主串用尽
return j < pattern.Length ? -1 : i - j;
}
#endregion