KMP算法

此文是严蔚敏的数据结构课程有关KMP算法相关课程 - KMP算法讲解P12 的理解记录。

模式串匹配原始算法

模式串匹配最原始的算法是：分别利用计数指针 i 和 j 指示主串 S 和模式串 T 中当前正待比较的字符位置。算法的基本思想是：从主串 S 的第 pos 个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后续字符；否则从主串 S 的下一个字符起再重新和模式串 T 的字符比较之。以此类推，直至模式串 T 中的每个字符依次和主串 S 中的一个连续的字符序列相等，则称匹配成功，函数值为和模式串 T 中第一个字符相等的字符在主串 S 中的序号，否则称匹配不成功，函数值为零。 其算法如下所示：
原始算法

int Index(SString S, SString T, int pos) {
    // 返回子串 T 在主串 S 中第 pos 个字符之后的位置。若不存在，则函数值为0。
    // 其中，T 非空，1 <= pos <= StrLength(S)。
    i = pos;    j = 1;
    while (i <= S[0] && j <= T[0]) {
        if (S[i] == T[j]){ ++i;    ++j; }  // 继续比较后继字符
        else { i = i - j + 2;    j = 1; }
    }
    if (j > T[0])    return i - T[0];
    else return 0;
} // Index

这种原始算法因为其 i 指针和 j 指针在不匹配的时候都需要回溯，我们可以得到在最坏情况下其的时间复杂度为 O(n * m)。所以便有了改进算法 - KMP算法

模式串匹配改进算法 - KMP算法

这种改进算法是 D.E.Knuth 与 V.r.Pratt 和 J.H.Morris 同时发现的，因此人们称它为 克努特 - 莫里斯 - 普拉特操作（简称为KMP算法）。此算法可以在 O(n + m) 的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程中出现字符串比较不等时，不需回溯 i 指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。

假设主串为 s1s2···sn ，模式串为 p1p2···pm ，为了实现改进算法，需要解决下述问题：当匹配过程中产生“失配”（即si != pj ）时，模式串“向右滑动”可行的距离多远，换句话说，当主串第 i 个字符与模式中第 j 个字符“失配”（即比较不等）时，主串中第 i 个字符（ i 指针不回溯）应与模式中哪个字符再比较？

假设此时应与模式串 T 中第 k (k < j)个字符继续比较，则模式串 T 中前 k - 1 个字符的子串必须满足下列关系式，且不可能存在 k’ > k 满足下列关系式
关系式①：p1p2···pk-1 = si-k+1 si-k+2···si-1
而已经得到的“部分匹配”的结果是
关系式②：pj-k+1 pj-k+2···sj-1 = si-k+1si-k+2···si-1
由关系式①和关系式②推得下列等式
关系式③：p1p2···pk-1 = pj-k+1 pj-k+2···pj-1

反之，若模式串中存在满足关系式③的两个子串，则当匹配过程中，主串 S 中的第 i 个字符与模式串 T 中第 j 个字符比较不等时，仅需将模式串 T 向右滑动至模式串 T 第 k 个字符和主串 S 中第 i 个字符对齐，此时，模式串 T 中头 k - 1 的子串 p1p2···pk-1 必定与主串中第 i 个字符之前的长度为 k - 1 的子串 si-k+1 si-k+2···si-1 相等，由此，匹配仅需从模式串 T 中第 k 个字符与主串 S 中第 i 个字符比较起继续进行。

若令 next[j] = k，则 next[j] 表明当模式串 T 中第 j 个字符与主串中相应字符“失配”时，在模式串 T 中需重新和主串 S 中该字符进行比较的字符的位置。由此引出模式串 T 的 next 函数的定义：

	0	当 j = 1 时
next[j] =	Max{k I 1 <k < j 且p1p2···pk-1 = pj-k+1 pj-k+2···pj-1 }	当此集合不空时
	1	其他情况

由此定义可推出下列模式串中的 next 函数值：

j	1	2	3	4	5	6	7	8
模式串	a	b	a	a	b	c	a	c
next[j]	0	1	1	2	2	3	1	2

在求得模式串 T 的 next 函数之后，匹配可如下进行：假设以指针 i 和 j 分别指示主串 S 和 模式串 T 中正待比较的字符，令 i 的初值为 pos，j 的初值为 1。若在匹配过程中 si = pj ，则 i 和 j 分别增 1，否则 i 不变，而 j 退到 next[j] 的位置在比较，若相等，则指针各自增 1，否则 j 再退到下一个 next 值的位置，依次类推，直至下列两种可能：

• 一种是 j 退到某个 next 值（next[next[···next[j]···]]）时字符比较相等，则指针各自增 1，继续进行匹配；
• 另一种是 j 退到值为零（即模式的第一个字符“失配”），则此时需将模式串 T 继续向右滑动一个位置，即从主串的下一个字符 si+1起和模式串 T 重新开始匹配。

KMP算法如下所示：它在形式上和原始算法极为相似。不同之处在于匹配过程中产生“失配”时，指针 i 不变，指针 j 退回到 next[j] 所指示的位置上重新进行比较，并且当指针 j 退至零时，指针 i 和指针 j 同时增 1。即若主串 S 的第 i 个字符和模式串 T 的第一个字符不等，应从主串的第 i + 1 个字符起重新进行匹配。

KMP算法

int Index_KMP(SString S, SString T, int pos) {
    // 利用模式串 T 的 next 函数求 T 在主串中第 pos 个字符之后的位置的KMP算法。
    // 其中，T 非空，1 <= pos <= StrLength(S)。
    i = pos;    j = 1;
    while (i <= S[0] && j <= T[0]) {
        if ( j == 0 || S[i] == T[j]){ ++i;    ++j; }  // 继续比较后继字符
        else { j = next[j]; }
    }
    if (j > T[0])    return i - T[0];
    else return 0;
} // Index_KMP

next 函数算法

KMP算法是在已知模式串的 next 函数值的基础上执行的，那么，如何求得模式串的 next 函数值呢？

从上述讨论可见，此函数值仅取决于模式串本身而和相匹配的主串无关。我们可从分析其定义出发，用递推的方法求得 next 函数值。

由定义得知: next[1] = 0
设 next[j] = k，这表明在模式串中存在下列关系：p1p2···pk-1 = pj-k+1 pj-k+2···pj-1
其中 k 满足 1 < k < j 的某个值，并且不可能存在 k’ > k 满足等式 p1p2···pk-1 = pj-k+1 pj-k+2···pj-1 ，此时 next[j+1] = ? 可能有两种情况：

1. 若 pk = pj ，则表明在模式串中 p1p2···pk = pj-k+1 pj-k+2···pj ，并且不可能存在 k’ > k 满足等式 p1p2···pk = pj-k+1 pj-k+2···pj，这就是说 next[j+1] = next[j] + 1 。
2. 若 pk != pj ，则表明在模式串中 p1p2···pk != pj-k+1 pj-k+2···pj ，此时可把求 next 函数值的问题看成是一个模式匹配的问题，整个模式串既是主串又是模式串，而当前在匹配过程中，已有 pj-k+1 = p1, pj-k+2 = p2,···，pj-1 = pk-1，则当 pk != pj 时应将模式串向右滑动至以模式串中的第 next[k] 个字符和主串中的第 j 个字符向比较。若 next[k] = k’，且 pj = pk’，则说明在主串中第 j + 1 个字符之前存在一个长度为 k’（即next[k]的最长子串，和模式串中从首字符起长度为 k’ 的子串相等），即 p1p2···pk = pj-k+1 pj-k+2···pj ( 1 < k’ < k < j)，这就是说 next[j+1] = k’ + 1，即 next[j+1] = next[k] + 1。同理若 pj != pk’，则将模式继续向右滑动直至将模式串中的第 next[k’] 个字符和 pj 对齐，······，依次类推，直至 pj 和模式串中的某个字符匹配成功或者不存在任何 k’(1 < k’ < j) 满足 p1p2···pk = pj-k+1 pj-k+2···pj，则 next[j + 1] = 1。

next 函数算法

void get_next(SString T, int next[]) {
    // 求模式串 T 的 next 函数值并存入数组 next。
    i = 1;  next[1] = 0;  j = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            ++i;  ++j;  next[i] = j;
        }else {
            j = next[j];
        }
    }   
}// get_next