KMP 算法学习笔记 (常见疑问解答)

导言: 本文旨在弄懂怎么去记忆和使用kmp算法进行字符串匹配, 而不强调理论上的证明. 所以文章更加偏向于如何从实例中理解算法的本质和灵活使用, 有些原理以及为什么都可以利用实际的例子去记忆, 并且相信这是对的就可以了, 不一定要从数学上真正理解或者真正证明.

参考文献: 算法导论 第二版

KMP框架: 朴素的暴力的字符串匹配很简单, 从目标字符串T (长度是n) 的第一个字符开始挨个试图去匹配模式字符串P (长度为m), 一旦失配, 那么继续从T的下一个字符开始重新匹配, 这个算法很简单但是效率也不高, 很明显时间复杂度是O(mn). 我们定义“有效位移”是每次失配的时候, 从当前匹配的第一个字符到下一次进行匹配的字符移动的距离, 对于朴素的字符串匹配算法,他每次失配以后的有效位移总是1. 那么KMP 算法认为失配的时候可以根据已经匹配的子串S (必定是T的后缀, 以及P的前缀) 的信息决定“有效位移”, 直接跳过一些没有必要的匹配的首字符, 从而提高时间效率. 这个”有效位移”可以由已经匹配的S串唯一决定(稍后解释为什么), 并且被称作前缀函数(更加具体的, 前缀函数是从S的长度到既是S自身真后缀又是S自身最长前缀的字符串长度的映射, 下文具体展开,** 注意前缀函数不直接是有效位移, 但是却是唯一决定了有效位移**). 假设我们已经有了前缀函数, 那么在朴素的字符串匹配的基础上我们利用前缀函数计算每次的有效位移, 这样前缀函数的计算O(m)加上匹配的时间O(n) 从而总的时间是O(n+m)

常见难点解答以及理解点:

(1) 为什么前缀函数求出的有效位位移保证了匹配算法的正确性

根据S计算出的有效位移的公式是:  有效位移 =  已经匹配的字符串S的长度 – 特殊子串长度. 这里的特殊子串是说S中前缀和后缀都相同的最长的子串,既是自身真后缀又是自身最长前缀的字符串。 比如ababa中的这个特殊字串就是aba.  那为什么这样的有效位移一定是对的呢, 这样跳过的那写字符真的没有必要去check吗? 我们看一个特殊的例子, 比如a b c d e f g 所有都不相同, 那么有效位移是 7 – 0  = 7 用这样的极端例子去记住有效位移的计算即可, 你想嘛, 已经匹配的所有字符都不一样的话, 就说明, 接下来的这些字符都不是a, 即使你一个一个匹配下去也就是马上就失配了, 于是可以放心的直接跳过,  这样的结果就是你一次性移动的有效位移使得你直接就跳到下一次可能的匹配, 其实从公式上看通过这个有效位移就是使得最长前缀和后缀重合, 那么这个就一定是下次匹配的开始.

(2) 为什么前缀函数要叫前缀函数

我个人是这么理解的: 已经匹配的子串S 必定是T的后缀, 以及P的前缀, 而匹配的过程就是拿T的后缀去和P的前缀去比. 如果去看算法导论的话, 还有另一个函数叫做后缀函数, 那么这个函数的输入其实是T的后缀,所以叫做后缀函数. 而这里的前缀函数是相对P讲的, 指的是根据P的前缀来定义的函数.

(3) 如何求前缀函数 next是有技巧的. 真因为该技巧才保证了前缀函数的线性时间复杂度O(m).

光是知道前缀函数的公式要在线性时间内求出前缀函数还是需要一定的技巧的. 就是递归调用前缀函数的之前的结果. 详见算法导论 (待续)

(4) 如何分析匹配的线性时间复杂度O(n).

这里需要理解摊还分析. 详见算法导论 (待续)

(5) 个人认为(3) (4)要真正理解以及正确的实现代码(比如在面试还是比赛当场没有任何参考资料的情况下)还是有一定难度, 平常的时候可以建议直接敲模版>_<, 要是碰到面试什么的可以暂时死记硬背一下, 虽然可能比较痛苦…… 当然用多了很熟手了的话则是另外一回事…..

(6) KMP前缀函数的小小应用

可以利用前缀函数next求出字符串的最短循环节. 设字符串长度是len, 那么(len – next[len]) 是字符串的最小循环节, if(len % (len – next[len]) == 0),  len / (len – next[len]) 就是循环的次数, 否则循环次数为1 , 也就是说最短循环节就是该字符串本身.

Written on May 18, 2013