记录KMP算法，记录其经典之处。。。

离开学校已经多年了，早已经不再抚弄那些陈旧的书籍。

周末，深圳的天气阴沉，老天这段时间总是很乐意显摆，动不动就给深圳人民来次几十年一遇的暴雨，似乎要把一年的雨水全部在这些天下完似的。

所以呆在家里面看电视，上网，实在也无聊。随手翻开大学时候的（数据结构，还留着啊，当初刚出来的时候总没有底气，总希望能够随时充电用）。看到了字符串的模式匹配一章。突然发现KMP算法是如此的经典。故记之。。。

在提KMP的经典之前，首先要提基本的模式匹配算法：

所谓模式匹配，简单点说就是对两字符串进行匹配，找出一个字符串在另一个字符串中的位置。

基本的模式匹配是这样的：

假设有字符串

S=S₁S_2......S_N（由于为了算法效率的需要，所以一般都把S[0]保存S的长度）

P=P₁P₂......P_M（同上）

其中（M<N），要求返回P在S中出现的位置。

所以算法要点如下：

假设从S中i点开始扫描（也就是从S[i]开始，此时用一个变量k=i），顺序比较S[i]和P[1],S[i+1]和P[2]。这样，当P进行到第j个字符也就是P[j]的时候，发现S[i+j-1]和P[j]不匹配，那么需要把S的指针i回朔到S起始的下一个字符也就是k+1继续比较。

如图：

以上就是模式匹配的基本算法，这种算法对于大多数的匹配来说基本是O(N+M)的时间复杂度。

但是对于如下的字符串：

S=0000000000000000000000000000001

P=000001

这种字符串来说，每次匹配失败都是在P到最后一个字符也就是j=M的时候，此时S的指针又必须回朔，导致大量的匹配。此时的时间复杂度是O(N*M)。

所以基本算法的时间复杂度是O(N*M)。当然了，对于大多数的匹配是不会有这么高的时间复杂度的，所以这种算法现在也在广泛使用，因为简单。

为了解决上述的问题，KMP算法被发现。

KMP算法的思想如下。匹配过程中，出现不匹配时，S的指针不进行回朔（原地不动），将P尽可能地向后移动一定的距离，再进行匹配。

如图：

从上图中我们看到，当S移动到i，P到j的时候失配。这时候i不回朔，而只是将P向前移动尽可能的距离，继续比较。

假设，P向右移动一定距离后，第k个字符P[k]和S[i]进行比较。

此时如上图，当P[j]和S[i]失配后，i不动，将P前移到K，让P[k]和S[i]继续匹配。现在的关键是K的值是多少？

通过上图，我们发现，因为黄色部分表示已经匹配了的结果（因为是到了S[i]和P[j]的时候才失配，所以S_i-j+1S_i-j+2…S_i-1 = P₁P₂…P_j-1，见黄色的部分）。所以有：

1、S_i-k+1S_i-k+2…S_i-1 = P_j-k+1P_j-k+2…P_j-1。

所以当P前移到K时，有：

2、S_i-k+1S_i-k+2…S_i-1 = P₁P₂…P_k-1。

通过1，2有

P_j-k+1P_j-k+2…P_j-1 = P₁P₂…P_k-1。

呵呵，此时我们的任务就是求这个k值了。。。

理解了这一点之后，终于能够发现此算法的经典了。

评论

1 楼 saieuler 2012-09-18  

每次都是学会了，过段时间又忘了