我所理解的KMP算法
作者：goal00001111（高粱）
始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
一．简单字符串模式匹配算法的缺陷
设有目标串T(target)和模式串P(pattern)，模式匹配是指在目标串T中找到一个与模式串P相等的子串。模式匹配成功是指在目标串T中找到了一个模式串P。
简单字符串模式匹配算法（也就是BF算法）的基本思想是：从目标串T的起始比较位置pos开始（在后面的案例中，我们默认pos = 0），和模式串P的第一个字符比较之，若匹配，则继续逐个比较后继字符，否则从串T的下一个字符起再重新和串P的字符比较之。依此类推，直至串P中的每个字符依次和串T中的一个连续的字符序列（即匹配子串）相等，则称匹配成功，返回该匹配子串的首字符下标；否则成匹配不成功，返回-1。
BF算法的思想很直接，也很容易理解，其时间复杂度为O（lenT*lenP），其中lenT和lenP分别为串T和串P的长度。
我们先给出代码，再做简要分析：
/*
函数名称：BFIndex
函数功能：简单字符串模式匹配算法，若目标串T中从下标pos起存在和模式串P相同的子串，则称匹配成功，返回第一个匹配子串首字符的下标；否则返回-1。
输入参数：const string & T ：目标串T
const string & P ：模式串P
int pos ：模式匹配起始位置
输出参数：int ：匹配成功，返回第一个匹配子串首字符的下标；否则返回-1。
*/
int BFIndex(const string & T, const string & P, int pos)
{
int i = pos;
int j = 0;
while (i < T.size() && j < P.size())
{
if (T[i] == P[j]) //如果当前字符匹配，继续比较后继字符
{
++i;
++j;
}
else //否则i，j回溯，重新开始新的一轮比较
{
i = i - j + 1;
j = 0;
//if (i > T.size() - P.size()) //一旦目标串剩余部分子串比模式串短，则无需再比较
// break;
}
}
if (j == P.size()) //匹配成功，返回第一个匹配子串首字符的下标
return i - j;
else
return -1;
}
我们发现，在某一轮比较中，一旦出现字符失配（即T[i] != P[j]），则需将i和j回溯，其中i回溯至i = i - j + 1，j回溯至j = 0。
这样产生了很多不必要的比较，例如（例1）：
string T = "aababaabaabc";
string P = "abaabc";
在第4轮比较中，T3T4T5T6T7 == P0P1P2P3P4，我将其简写为T[3…7] == P[0…4]（后面的都这样表示），但T[8] != P[5]，出现字符失配，需要将i和j回溯，使得i = 4， j = 0。
而在第4轮比较中，我们已经得到了T[6…7] == P[3…4]，又P[0…1] == P[3…4]，相当于T[6…7]和P[0…1]已经间接地比较过，而且字符匹配了，我们无需进行从i =6， j = 0开始的重复比较。
实际上，当T[8] != P[5]，即在i = 8， j = 5处出现字符失配时，我们无需将i回溯，只需将j回溯至failure[j]（此时failure[5] = 2）处即可。即当T[8] != P[5]时，我们可以跳过比较T[6…7]和P[0…1]（因为它们已经间接地比较过了），直接比较字符T[8]和P[2]，这样可以省去很多不必要的回溯和比较，时间复杂度达到O（lenT+lenP）。这就是KMP算法的核心思想。
二．高效的KMP算法
现在继续剖析KMP算法。
我在上文提到当T[i] != P[j]时，我们无需将i回溯，只需将j回溯至failure[j]处即可。我们称failure[j]为模式串P下标j的失效函数。
失效函数的值failure[j]是指当T[i] != P[j]时，接下来与T[i]进行比较的模式串P的元素下标。如上面的例子，当T[8] != P[5]时，因为T[6…7] == P[3…4] == P[0…1]，我们可以跳过比较T[6…7]和P[0…1]，直接比较字符T[8]和P[2]，所以failure[5] = 2。
如果你对失效函数还不太理解，我再举一些例子。
仍然以上面提供的目标串T和模式串S为例，当出现T[1…3] == P[0…2]，但T[4] != P[3]时，若采用BF算法，则需要将i和j回溯，使得i = 2， j = 0。
而采用KMP算法，则无需将i回溯，j也不需要回溯至j = 0，而只需回溯至j = failure[j]。那如何得知failure[j]的值呢？观察模式串P，我们发现P[2] == P[0]，因为T[3] == P[2]，所以T[3] == P[0]，相当于我们已经间接地比较过T[3] 和P[0]了，无需重复比较，接下来可以直接比较T[4]和P[1]，所以failure[3] = 1。
再看一个简单的例子（例2）：
string T = "aabcabaababc";
string P = "ababc";
当出现T[0] == P[0]，但T[1] != P[1]时，要保证i不变，必须将j回溯至j = 0，然后比较T[1] 和P[0]，所以failure[1] = 0。
同样的，当出现T[4…6] == P[0…2]，但T[7] != P[3]时，要保证i不变，必须将j回溯至j = 0（为什么？好好想想！），然后比较T[7] 和P[0]，所以failure[3] = 0。
那么，如果模式串P的第一个元素就不匹配，即T[i] != P[0]又该怎么办呢？j已经最小，没办法再往前回溯了，下一次比较必须使i自增1。这是一种特殊的情况，考虑到C语言中的数组下标从0开始，为了表示区别，我们设failure[0] = -1。很明显当failure[j] != -1时，在进行下一次比较之前，我们无需改变i的值；而当failure[j] == -1时，在进行下一次比较之前，必须先使i自增1。
我们继续分析例2，当出现T[1…2] == P[0…1]，但T[3] != P[2]时，要保证i不变，必须将j回溯至j = 0，然后比较T[1] 和P[0]——看上去好像一切都顺理成章，但是请等等！ 经比较T[1] == P[0]，经观察P[2] == P[0]，我们还有必要再去比较T[1] 和P[0]吗？当然不需要，我们应该直接比较T[2] 和P[0]才对！所以failure[2] = -1。
举了一大堆例子，苦于没有图象对照，想必各位看官已经看得头都大了！到底如何求模式串P的失效函数failure[j]，可能很多人还是一头雾水（PS：我计划做一个教学视频，到时候图文声并茂，一定会帮助你理解的，记得随时关注博客，等待观看哦）。据考证，失效函数failure[j]是模式串P本身的属性，与目标串T无关，而且从不同的角度分析模式串P可以得到失效函数的不同表示方法。网络上此类文章可谓汗牛充栋，我的关于失效函数failure[j]的理解，与网友A_B_C_ABC 在其博文《KMP字符串模式匹配详解》（http://blog.csdn.net/A_B_C_ABC/archive/2005/11/25/536925.aspx）中所论述的“第一种表示方法”极为相似，如果你不想读我的文字，可以先去看A_B_C_ABC贴的图片，回过头再看我的文章，也许会明白我的意思——不会作图的下场啊！555
现在去A_B_C_ABC的博客看图！
。。。。。。
现在明白失效函数failure[j]的意义了吧？也应该知道如何求解failure[j]了吧？
总结一下吧：
先看失效函数的意义。
设在目标串T中查找模式串P，若T[i] != P[j]，则将j回溯至失效函数值failure[j]处，那failure[j]可以取到哪些值呢？
① failure[0]= -1，表示T[i]和P[0]间接比较过了，且T[i] != P[0]，接下来比较T[i+1]和P[0]；
② failure[j] = 0，表示比较过程中产生了不相等，接下来比较T[i]和P[0]；
③ failure[j] = k，其中0 < k < j，表示T[i]之前的k个字符与P中的前k个字符已经间接比较过了，且P[0…k-1] == P[j-k…j-1] == T[i-k…i-1]，接下来比较T[i]和P[k]。
除了上述三种情况，failure[j]不可能取到其他值。
那么如何求解失效函数failure[j]的值呢？
从上述讨论可见，失效函数failure[j]的值仅取决于模式串P本身，与目标串T无关。
① failure[0]= -1：考虑到C语言中的数组下标从0开始，模式串P的首字符的失效函数值规定为-1；
② failure[j] = -1：若P[j] == P[0]，且P[0…k-1] != P[j-k…j-1]，或P[0…k] == P[j-k…j]，其中0 < k < j。
如：P = "abcaabcab"。
因为P[3] == P[0]，且P[0] != P[1]，P[0…1] != P[1…3]，则failure[3] = -1；
又因为P[7] == P[0]，且P[0…3] == P[4…7]，则failure[7] = -1；
③ failure[j] = k：若P[0…k-1] == P[j-k…j-1]，且P[k] != P[j]，其中0 < k < j。
如：P = "abcaabcab"。
因为P[0] == P[3]，且P[1] != P[4]，则failure[4] = 1；
又因为P[0…3] == P[4…7]，且P[4] != P[8]，则failure[8] = 4；
④ failure[j] = 0：除（1）（2）（3）的其他情况。
如：P = "abcaabcab"中，failure[1] = failure[2] = failure[5] = failure[6] = 0；
算法思路：
KMPIndex函数：
KMP算法在形式上和BF算法即为相似。不同之处仅在于：当匹配过程中产生“失配”时，目标串T指示标志i不变，模式串P指示标志j回溯至failure[j]所指示的位置，并且当j回溯至最左端（即failure[j] == -1）时，使j = 0，i自增1，。
GetFailure函数：
根据failure[j]的定义，我们先规定failure[0] = -1；然后遍历模式串P，依次计算各个元素的失配函数值。
设已有k == 0；或0 < k < j，且P[0…k-1] == P[j-k…j-1]；我们比较P[k]和 P[j]：
若P[k] == P[j]，则由failure[j]的定义可知failure[j] = failure[k]，之后k和j均自增1，继续比较后继字符；
若P[k] != P[j]，则failure[j] = k。很明显之后不能直接比较后继字符；而需要将k回溯，直至找到使得P[0…k] == P[j-k…j]的最大k值，才可以让k和j均自增1，继续比较后继字符。
那么如何将k快速回溯到适当的位置呢？
我们设h = failure[k]，很明显有：P[0…h-1] == P[k-h…k-1] == P[j-h…j-1]。
若P[h] == P[j]，那h就是满足条件的最大k值。
若P[h] != P[j]，则再在串P[0…h]中寻找更小的failure[h]。如此递推，有可能还需要以同样的方式再缩小寻找范围，直到failure[h] == -1才算失败。
若failure[h] == -1，则相当于k已经回溯到了模式串P的最左端，可以让k和j均自增1，继续比较后继字符。
实现代码如下：
/*
函数名称：KMPIndex
函数功能：Knuth－Morris－Pratt算法，若目标串T中从下标pos起存在和模式串P相同的子串，则称匹配成功，返回第一个匹配子串首字符的下标；否则返回-1。
输入参数：const string & T ：目标串T
const string & P ：模式串P
int pos ：模式匹配起始位置
输出参数：无
返回值：int ：匹配成功，返回第一个匹配子串首字符的下标；否则返回-1。
*/
int KMPIndex(const string & T, const string & P, int pos)
{
int *failure = new int[P.size()];
Getfailure(P, failure); //计算模式串P的失配函数failure[]
int i = pos;
int j = 0;
while (i < T.size() && j < P.size())
{
if (T[i] == P[j]) //如果当前字符匹配，继续比较后继字符
{
++i;
++j;
}
else //否则保持i不变，将j回溯至failure[j]，开始新的一轮比较
{
j = failure[j];
if (j == -1) //若j回溯至最左端，则使j = 0，i自增1
{
j = 0;
++i;
}
}
}
delete []failure;
if (j == P.size()) //匹配成功，返回第一个匹配子串首字符的下标
return i - j;
else
return -1;
}
/*
函数名称：Getfailure
函数功能：计算模式串P的失配函数，并存入数组failure[]
输入参数：const string & P ：模式串P
int failure[]：模式串P的失配函数
输出参数：int failure[]：模式串P的失配函数
返回值：无
*/
void Getfailure(const string & P, int failure[])
{
failure[0] = -1; //模式串P的首字符的失配函数值规定为-1
for (int j=1, k=0; j<P.size(); j++, k++)//遍历模式串P，计算失配函数值
{
//若P[0…k-1] == P[j-k…j-1]，且P[k] == P[j]，则failure[j] = failure[k]，并继续比较后继字符
if (P[k] == P[j])
{
failure[j] = failure[k];
}
else //否则保持j不变，将k回溯至failure[k]
{
failure[j] = k; //若P[0…k-1] == P[j-k…j-1]，且P[k] != P[j]，则failure[j] = k
//寻找使得P[0…k] == P[j-k…j]的最大k值，才可以继续比较后继字符
while (k >= 0 && P[k] != P[j])//将k回溯至P[k] == P[j]或最左端，以进行下一轮比较
k = failure[k];
}
}
//以下代码输出failure[i]
for (int i=0; i<P.size(); i++)
cout << failure[i] << " ";
cout << endl;
}
我们刚才讨论的失效函数中有一个很巧妙的地方，那就是除了failure[0] = -1以外，模式串P中还有多处failure[j]可以等于-1，这就避免了重复比较T[i]和P[0]，可以直接比较T[i+1]和P[0]。但是最初接触到这个算法的时候，我被这个“巧妙之处”足足折腾了半天——只因为效率上的一点点提高，却带来了理解上的巨大困难——真是得不偿失啊！
那么有没有更好理解的失效函数呢？当然有！
评论