找出 P 的所有前缀集合 CP,找出 P 的所有后缀集合 CS,求 CP 和 CS 的交集中长度最大的元素,称之为 P 的『最长前后缀』。
下面的代码实现了前缀计算函数:
下面的代码实现了 KMP 算法主体部分:
给定长度为 m 的模式 P,其前缀函数 π。证明:对 ,有 。
证: 我们先证明 ,也就是要证明对于 中的每一个元素 , 。
当 时,,
由定义
假设,当 时,;
当 时,
成立。
接下来我们用反正法证明 。
假设 ,我们取非空集合 中最大的元素 m,
取
由上面的证明,我们知道
,
,这与 和 的取法相矛盾(要么 m 不是非空集合 中最大的,要么 n 不是 中最小的)
假设不成立,即
综上所述,引理结论成立,证毕。
给定长度为 m 的模式 P,其前缀函数 π。证明:对 ,如果 ,那么 。
证: 令 ,那么 , ,
(通过把 , 的最后一个字符去掉)
由引理 32.5 可得
证毕。
对 ,定义 的子集 如下:
给定长度为 m 的模式 P,其前缀函数 π,那么对 ,有 。
证: 当 时,由 知,不存在 , ,使得
当 时,
,有
即
另一方面,由上我们知道 ,令 ,由引理 32.6,得
由 , 两式,我们得到
即
由 , 两式,可得
综上所述,推论得证。
1.《算法导论》