Matrix67的OI点滴（三）KMP算法.doc

Matrix67的OI点滴（三）：KMP算法 ??? 如果机房马上要关门了，或者你急着要和MM约会，请直接跳到第六个自然段。 ? ??? 我们这里说的KMP不是拿来放电影的（虽然我很喜欢这个软件），而是一种算法。KMP算法是拿来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字符串A=Im 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]，KMP的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配（从而使得i和j能继续增加）。我们看一看当i=j=5时的情况。 ? ??? i = 1 2 3 4 5 6 7 8 9 ……??? A = a b a b a b a a b a b …??? B = a b a b a c b??? j = 1 2 3 4 5 6 7 ? ??? 此时，A[6]B[6]。这表明，此时j不能等于5了，我们要把j改成比它小的值j。j可能是多少呢？仔细想一下，我们发现，j必须要使得B[1..j]中的头j个字母和末j个字母完全相等（这样j变成了j后才能继续保持i和j的性质）。这个j当然要越大越好。在这里，B[1..5]=ababa，头3个字母和末3个字母都是aba。而当新的j为3时，A[6]恰好和B[4]相等。于是，i变成了6，而j则变成了4： ? ??? i = 1 2 3 4 5 6 7 8 9 ……??? A = a b a b a b a a b a b …??? B =???? a b a b a c b??? j =???? 1 2 3 4 5 6 7 ? ??? 从上面的这个例子，我们可以看到，新的j可以取多少与i无关，只与B串有关。我们完全可以预处理出这样一个数组P[j]，表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时，新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。 ??? 再后来，A[7]=B[5]，i和j又各增加1。这时，又出现了A[i+1]B[j+1]的情况： ? ??? i = 1 2 3 4 5 6 7 8 9 ……??? A = a b a b a b a a b a b …??? B =???? a b a b a c b??? j =???? 1 2 3 4 5 6 7 ? ??? 由于P[5]=3，因此新的j=3： ? ??? i = 1 2 3 4 5 6 7 8 9 ……??? A = a b a b a b a a b a b …??? B =???????? a b a b a c b??? j =