KMP算法详解.doc

如果机房马上要关门了,或者你急着要和 MM 约会,请直接跳到第六个自然段。我们这里说的 KMP 不是拿来放电影的( 虽然我很喜欢这个软件), 而是一种算法。 KM P 算法是拿来处理字符串匹配的。换句话说,给你两个字符串,你需要回答, B 串是否是 A 串的子串( A 串是否包含 B串) 。比如,字符串 A="I'm matrix67" ,字符串 B="matrix" ,我们就说 B是A 的子串。你可以委婉地问你的 MM :“假如你要向你喜欢的人表白的话, 我的名字是你的告白语中的子串吗? ”解决这类问题,通常我们的方法是枚举从 A 串的什么位置起开始与 B 匹配,然后验证是否匹配。假如 A 串长度为 n,B 串长度为 m ,那么这种方法的复杂度是 O (mn) 的。虽然很多时候复杂度达不到 mn (验证时只看头一两个字母就发现不匹配了) ,但我们有许多“最坏情况”, 比如, A= "aaaaaaaaaaaaaaaaaaaaaaaaaab" , B="aaaaaaaab" 。我们将介绍的是一种最坏情况下 O(n) 的算法(这里假设 m<=n ) ,即传说中的 KMP 算法。之所以叫做 KMP ,是因为这个算法是由 Knuth 、 Morris 、 Pratt 三个提出来的,取了这三个人的名字的头一个字母。这时,或许你突然明白了 AVL 树为什么叫 AVL ,或者 Bellman-Ford 为什么中间是一杠不是一个点。有时一个东西有七八个人研究过, 那怎么命名呢?通常这个东西干脆就不用人名字命名了,免得发生争议,比如“ 3x+1 问题”。扯远了。个人认为 KMP 是最没有必要讲的东西, 因为这个东西网上能找到很多资料。但网上的讲法基本上都涉及到“移动(shift) ”、“ Next 函数”等概念,这非常容易产生误解(至少一年半前我看这些资料学****KMP 时就没搞清楚) 。在这里,我换一种方法来解释 KMP 算法。假如, A="abababaababacb" , B="ababacb" , 我们来看看 KMP 是怎么工作的。我们用两个指针 i和j 分别表示, A[i-j+ 1..i] 与 B[1..j] 完全相等。也就是说, i 是不断增加的,随着 i 的增加 j 相应地变化,且 j 满足以 A[i] 结尾的长度为 j 的字符串正好匹配 B 串的前 j 个字符(j 当然越大越好) ,现在需要检验 A[i+1] 和 B[j+1] 的关系。当 A[i+1]=B[j+1] 时, i和j 各加一;什么时候 j=m 了,我们就说 B是A 的子串( B 串已经整完了) ,并且可以根据这时的 i 值算出匹配的位置。当 A[i+1]<>B[j+1] , KM P 的策略是调整j 的位置(减小j值)使得 A[i-j+1..i] 与 B[1..j] 保持匹配且新的 B[j+1] 恰好与 A[i+1] 匹配( 从而使得 i和j 能继续增加)。我们看一看当 i=j=5 时的情况。 i=123456789 …… A=abababaabab… B=ababacbj=1234567 此时, A[6]<>B[6] 。这表明,此时 j 不能等于 5 了,我们要把 j 改成比它小的值 j'。 j'可能是多少呢?仔细想一下, 我们发现, j' 必须要使得 B[1..j] 中的头 j' 个字母