KMP算法及其正确性证明


找出 P 的所有前缀集合 CP,找出 P 的所有后缀集合 CS,求 CP 和 CS 的交集中长度最大的元素,称之为 P 的『最长前后缀』。


算法实现及分析

下面的代码实现了前缀计算函数:

def COMPUTE_PREFIX(P):
    pi = []
    pi.insert(0, 0)

    k = 0
    for q in range(1, len(P)):
        while k > 0 and P[k] != P[q]:
            k = pi[k - 1]

        if P[k] == P[q]:
            k += 1

        pi.insert(q, k)

    return pi

下面的代码实现了 KMP 算法主体部分:

def KMP_MATCHER(T, P):
    pi = COMPUTE_PREFIX(P)
    q = 0   # 已匹配的字符数

    for i in range(0, len(T)):
        while q > 0 and P[q] != T[i]:
            q = pi[q - 1]

        if P[q] == T[i]:
            q += 1  # 下一个字符也匹配

        if q == len(P):
            print("Pattern occurs from index %s" % (i - len(P) + 1))
            # q = 0 # T 中已匹配的字符不可重复匹配
            q = pi[q - 1]   # T 中已匹配的字符可重复匹配

正确性证明

* 引理 32.5(前缀函数迭代引理)

给定长度为 m 的模式 P,其前缀函数 π。证明:对 ,有

证: 我们先证明 ,也就是要证明对于 中的每一个元素

时,
由定义

假设,当 时,

时,



成立。

接下来我们用反正法证明

假设 ,我们取非空集合 中最大的元素 m,

由上面的证明,我们知道







,这与 的取法相矛盾(要么 m 不是非空集合 中最大的,要么 n 不是 中最小的)
假设不成立,即

综上所述,引理结论成立,证毕。


* 引理 32.6

给定长度为 m 的模式 P,其前缀函数 π。证明:对 ,如果 ,那么

证: 令 ,那么

(通过把 , 的最后一个字符去掉)

由引理 32.5 可得

证毕。


* 定义

,定义 的子集 如下:


* 推论 32.7

给定长度为 m 的模式 P,其前缀函数 π,那么对 ,有

证: 当 时,由 知,不存在 ,使得

时,
,有

另一方面,由上我们知道 ,令 ,由引理 32.6,得

两式,我们得到


两式,可得

综上所述,推论得证。


参考资料

1.《算法导论》