三．更好理解的失效函数
接下来我们看看另一些常见的失效函数表示方法。
在严蔚敏和吴伟民编著的《数据结构（C语言版）》（清华大学出版社）一书中，采用了一种比较简单的失效函数表示方法。它的定义与前面讲的失效函数差不多，只是把上述的四种情况简化为三种情况，将②和③合并为同一种类型，即若P[0…k-1] == P[j-k…j-1]，其中0 < k < j，则failure[j] = k，而不论P[k] 是否等于 P[j]。这样模式串P中就只有failure[0] = -1了，失效函数表示方法得到了简化——当然效率稍微有所降低。
采用这种失效函数表示方法，在求解失效函数时，可以利用简单的递推，根据failure[j]来得到failure[j+1]。
原理如下：
先给出两个概念：若存在0 <= k < j，且使得P[0…k] == P[j-k…j]的最大整数k，我们称P[0…k]为串P[0…j]的前缀子串，P[j-k…j]为串P[0…j]的后缀子串。
从failure[j]的定义出发，计算failure[j]就是要在串P[0…j]中找出最长的相等的前缀子串P[0…k]和后缀子串P[j-k…j]，这个查找的过程实际上仍是一个模式匹配的过程，只是目标和模式现在是同一个串P。
我们可以用递推的方法求failure[j]的值。
设已有failure[j] = k，则有0 < k < j，且P[0…k-1] == P[j-k…j-1]。接下来：
若P[k] == P[j]，则由failure[j]的定义可知failure[j+1] = k + 1 = failure[j] + 1；
若P[k] != P[j]，则可以在前缀子串P[0…k]中寻找使得P[0…h-1] == P[k-h…k-1]的h，这时存在两种情况：
① 找到h，则由failure[j]的定义可知failure[k] = h，故P[0…h-1] == P[k-h…k-1] == P[j-h…j-1]，即在串P[0…j]中找到了长度为h的相等的前缀子串和后缀子串。
这时若P[h] == P[j]，则由failure[j]的定义可知failure[j+1] = h + 1 = failure[k] + 1 = failure[failure[j]] + 1；
若P[h] != P[j]，则再在串P[0…h]中寻找更小的failure[h]。如此递推，有可能还需要以同样的方式再缩小寻找范围，直到failure[h] == -1才算失败。
② 找不到h，这时failure[k] == -1，即k已经回溯到k = failure[k] = -1，所以failure[j+1] = k + 1 = 0。
依据以上分析，仿照KMP算法，可以得到计算failure[j]的算法，其对应的KMPIndex函数不变。
代码如下：
/*
函数名称：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; j<P.size(); j++)//遍历模式串P，计算失配函数值
{
int k = failure[j-1]; //利用failure[j-1]递推failure[j]，k指向failure[j-1]
while (k >= 0 && P[k] != P[j-1])//将k回溯至P[k] == P[j-1]或k == -1，以进行下一轮比较
k = failure[k];
//现在可以确保P[0…k] == P[j-k-1…j-1]，则failure[j] = k + 1（若k == -1，则failure[j] = 0）
failure[j] = k + 1;
}
//以下代码输出failure[i]
for (int i=0; i<P.size(); i++)
cout << failure[i] << " ";
cout << endl;
}
前面定义的失效函数在某些情况下尚有缺陷。例如当模式串P = "aaaaaaaaaab"时，若T[i] != P[9]，因为failure[9] = 8，所以下一步要将T[i] 和 P[8]比较；依此类推还要比较P[7]，P[6]，。。。，P[0]。实际上，因为它们都相等，所以当T[i] != P[9]时，可以直接比较T[i] 和 P[0]。也就是说，若按上述定义得到failure[j] = k，且P[j] == P[k]时，则当T[i] != P[j]时，不需要再比较T[i] 和 P[k]，可以直接比较T[i] 和 P[failure[k]]，即此时的failure[j]应该等于failure[k]。由此我们可以在原来计算失效函数算法的基础上加上一条语句，对失效函数值进行修正，以得到更高效的KMP算法。而且我们可以检验修正后的失效函数值与用第一种方法得到的失效函数值是一样的。
计算失效函数修正值的代码如下：
void Getfailure2(const string & P, int failure[])
{
failure[0] = -1; //模式串P的首字符的失效函数值规定为-1
for (int j=1; j<P.size(); j++)//遍历模式串P，计算失效函数值
{
int k = failure[j-1]; //利用failure[j-1]递推failure[j]，k指向failure[j-1]
while (k >= 0 && P[k] != P[j-1])//将k回溯至P[k] == P[j-1]或k == -1，以进行下一轮比较
k = failure[k];
//现在可以确保P[0…k] == P[j-k-1…j-1]，则failure[j] = k + 1（若k == -1，则failure[j] = 0）
failure[j] = k + 1;
}
//对失效函数值进行修正，可以得到更高效的KMP算法
for (int j=1; j<P.size(); j++)
{
if (P[j] == P[failure[j]])
failure[j] = failure[failure[j]];
}
//以下代码输出failure[i]
for (int i=0; i<P.size(); i++)
cout << failure[i] << " ";
cout << endl;
}
四．另类的KMP算法
在殷人昆等人编著的《数据结构（用面向对象方法与C++描述）》（清华大学出版社）一书中，用到了另外一种表示失效函数的方法。该方法与前述两种方法的区别在于，当T[i] != P[j]时，模式串P的下标j不是回溯至failure[j]，而是回溯至failure[j-1]+1，所以它的KMPIndex函数和GetFailure函数都与前面的有所不同。
该书对失效函数failure[j]的定义如下：
① failure[j] = k，其中0 <= k < j，且使得P[0…k] == P[j-k…j]的最大整数；
② failure[j] = -1，其他情况。
如：P = "abcaabcab"。
j = 0时，没有满足0 <= k < j的k存在，故failure[0] = -1；
j = 1时，可取k = 0，但P[0] != P[1]，k不符合要求，故failure[1] = -1；
j = 2时，可取k = 0或1，但P[0] != P[2]，且P[0…1] != P[1…2]，k不符合要求，故failure[2] = -1；
j = 3时，可取k = 0，1或2：P[0] == P[3]，P[0…1] != P[2…3]，P[0…2] != P[1…3]，故failure[3] = k = 0；
j = 4时，可取k = 0，1，2或3：P[0] == P[4]，P[0…1] != P[3…4]，P[0…2] != P[2…4]，P[0…3] != P[1…4]，故failure[4] = k = 0；
j = 5时，可取k = 0。。4：P[0] != P[5]，P[0…1] == P[4…5]，P[0…2] != P[3…5]，P[0…3] != P[2…5]，P[0…4] != P[1…5]，故failure[5] = k = 1；
其他的以此类推可以得到failure[6] = 2；failure[7] = 3；failure[8] = 1。
设若在进行某一趟匹配比较时在模式串P的j位失配，即T[i] != P[j]，如果j > 0，因为P[failure[j-1]] == P[j-1] == T[i-1]，即已经间接地知道了P[0…failure[j-1]]是匹配的，那么我们只需将串P的下标j回溯至failure[j-1]+1，串T的下标i不回溯，仍指向上一趟失配的字符；如果j == 0，则让串T的下标i前进一位，串P的起始比较位置回溯到P[0]，继续做匹配比较。
如何正确地计算出失效函数failure[j]，是实现KMP算法的关键。
从failure[j]的定义出发，计算failure[j]就是要在串P[0…j]中找出最长的相等的前缀子串P[0…k]和后缀子串P[j-k…j]，这个查找的过程实际上仍是一个模式匹配的过程，只是目标和模式现在是同一个串P。
我们可以用递推的方法求failure[j]的值（此方法与上文介绍的严蔚敏教授书中的方法极为相似，只有一处不同，请注意区别）。
设已有failure[j] = k，则有0 <= k < j，且P[0…k] == P[j-k…j]。
若P[k+1] == P[j+1]，则由failure[j]的定义可知failure[j+1] = k + 1 = failure[j] + 1；
若P[k+1] != P[j+1]，则可以在前缀子串P[0…k]中寻找使得P[0…h] == P[k-h…k]的h，这时存在两种情况：
① 找到h，则由failure[j]的定义可知failure[k] = h，故P[0…h] == P[k-h…k] == P[j-h…j]，即在串P[0…j]中找到了长度为h + 1的相等的前缀子串和后缀子串。
这时若P[h+1] == P[j+1]，则由failure[j]的定义可知failure[j+1] = h + 1 = failure[k] + 1 = failure[failure[j]] + 1；
若P[h+1] != P[j+1]，则再在串P[0…h]中寻找更小的failure[h]。如此递推，有可能还需要以同样的方式再缩小寻找范围，直到failure[h] == -1才算失败。
② 找不到h，这时failure[k] == -1。
依据以上分析，仿照KMP算法，可以得到计算failure[j]的算法。
/*
函数名称：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 if (j == 0) //如果j == 0，则让目标串T的下标i前进一位
++i;
else //否则下一趟比较时模式串P的起始比较位置是P[failure[j-1]+1]，目标串T的下标i不回溯
j = failure[j-1] + 1;
}
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; j<P.size(); j++)//遍历模式串P，计算失配函数值
{
int k = failure[j-1]; //利用failure[j-1]递推failure[j]，k指向failure[j-1]
while (k >= 0 && P[k+1] != P[j])//将k回溯至P[k+1] == P[j]或k == -1，以进行下一轮比较
k = failure[k];
if (P[k+1] == P[j]) //若P[0…k] == P[j-k…j-1]，且P[k+1] == P[j]，则failure[j] = k + 1
failure[j] = k + 1;
else //没有找到满足条件的k
failure[j] = -1;
}
//以下代码输出failure[i]
for (int i=0; i<P.size(); i++)
cout << failure[i] << " ";
cout << endl;
}
这样我们就学习了三种失效函数的表示方法，虽然它们对应的KMP算法代码略有不同，但其本质是一样的，就是避免回溯目标串T的下标i，并使得模式串P的下标j回溯到正确位置。同样的，不管你用什么代码来实现求解失效函数的算法，其本质都是模式串内部的模式匹配，采用递推的方式，寻找最大的相同子串。
参考文献：
1.《数据结构（C语言版）》（清华大学出版社）严蔚敏，吴伟民编著
2.《数据结构（用面向对象方法与C++描述）》（清华大学出版社）殷人昆等人编著
3.《KMP字符串模式匹配详解》来自网友A_B_C_ABC的博客
（http://blog.csdn.net/A_B_C_ABC/archive/2005/11/25/536925.aspx）
4.《KMP算法中Next[]数组求法》作者：剑心通明
（http://www.bsdlover.cn/html/21/n-3021.html）
评论