KMP算法研究与实现

摘要：文字是传播信息的关键载体之一，是表达人类情感的重要方式，更是传承文化的最关键最基本的手段。理所当然，文本编辑程序是计算机中最重要的应用之一。自从计算机被发明以来，字符，字符串，文本，就一直于人类打着交道。在文本编辑程序中，经常会出现要搜索一段特定文字以及对其位置定位的情况，当文本内容庞大，或者要搜索的内容出现相当频繁时，良好的搜索算法对效率的提高就相当可观了。该文研究了效率极高的KMP字符串匹配算法，并使用C语言对算法进行了实现。

关键词：查找搜索；字符串匹配；KMP算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）20-4696-03

文本，一直是计算机这一领域中最基本的元素，无论是计算机刚诞生的年代，还是如今多媒体技术绚烂夺目的时代，文本一直都作为奠基性质的元老角色而存在着。

在对文本的编辑中，会遇到需要查找匹配特定模式的情况。比如，在一个文本文件中查找“ABC”这一小段，或者查找“不知道”这一词语。当文本的内容比较少时，人们可以通过简单的逐行查找来找到匹配的特定模式，然而，当文本具备一定的规模后，在其中查找特定的模式就足以令人抓狂了。

在当下这个信息大爆炸的时代，拥有大规模内容的文本实在不在少数，无论是金融界、文学界、政界还是计算机专业界，每天面对大量的文字信息实在令人欲罢不能，在其中寻找重要的关键词、关键句或者关键段落时，更是令人痛不欲生，即使是交给计算机去做，也需耗费大量的开销。因此，设计出一种好的算法，以高效地查找大容量文本文件中的特定匹配模式，不仅可以大大提高文本编辑的响应性能，还能改善人类的生活。

此外，随着学科之间交叉性的提高，很多领域也需要在大量的信息中查找某些特定模式及其出现的位置，例如DNA测序定位、海洋数据查询、高效搜索引擎等。

幸运的是，目前已经有了高效的字符串匹配算法，并且，此类算法仍在不断发展进化，向着更高的效率进发。

在本文中，作者研究分析了效率高超的KMP字符串匹配算法，并使用C语言对其进行了实现。

1 KMP算法研究与分析

历史上人们通过对字符串的研究而得出的字符串匹配问题的算法很多，其中很重要的一类匹配算法分为两步：第一步先对要匹配的模式进行一些预处理，第二步再寻找模式在全文本中的所有有效位移（即匹配）。KMP算法即是其中最高效的算法之一。

KMP字符串匹配算法，是由Knuth、Morris和Pratt三人设计的线性时间字符串匹配算法。假设要搜寻的模式有m个字符单位，整个文本有n个字符单位（一般来说n > m），则KMP算法所用时间花销在n+m这个数量级上，比起很多其他的算法要快不少。

KPM算法简单来说，可以从以下的事实获得灵感：对于在文本中搜寻特殊模式的情形来说，文本所包含的的信息毫无疑问比起特定模式要多得多，其不确定信息也更多。比如，在很长的文本中，下一个出现的字符可能是任何字符，变化可能会很大，然而，对于较短的确定的特定模式来说，在模式中出现的字符却基本上是确定的，因为模式是特别选出的，而且模式比起文本要短得多。一个最常见的例子就是在谷歌中搜寻“平板电脑”这一关键词，很明显，我们对“平板电脑”这四个字中所包含的信息可以说几乎完全确定，而对于在互联网中会出现什么样的网站能匹配这次搜索却包含着极大的不确定性。

因此，可以先对特定模式进行分析，得出所需要的信息，从而利用这些信息来加快匹配速度。

KMP的核心思想，便是充分利用特定模式本身所包含的信息，通过对特定模式的预处理而得出一个前缀函数，从而能够在对文本的匹配搜索中避免一般搜索所花费的无用功。

首先，让我们来看一下什么是前缀函数。

一个字符串的前缀相信不难理解，比如“abc”的前缀可以是“a”也可以是“ab”。在这里，前缀都指的是严格意义上的前缀，比如在刚刚的例子中，“abc”就不是字符串“abc”的前缀。

KMP的前缀函数则是包含有模式与其自身的位移进行匹配的信息的函数。通过前缀函数的生成，我们可以获得特定模式中以每一位字符所引领的前缀匹配原来特定模式的位移，并且通过这个位移，我们可以充分利用特定模式中先前已经与文本比较过的前缀所包含的信息，从而能快速准确地递归得出下一个最大匹配字符数。

以上的描述可以通过以下这个简单的例子来说明：

假设我们的特定模式为“abcabcde”，可以看出，若此模式在搜索匹配时，已经有“abcabc”与文本中的信息匹配上了，却在其后一位不匹配，此时，我们可以充分利用其本身所包含的信息，即“abc”这一前缀可以匹配“abcabc”的后三位，因此，我们可以立即将原模式“abcabcde”在此时文本中进行匹配的位置向文本结尾处移三位，从而以“abc”已经匹配的事实继续检验下一位是否匹配，因为事实上在搜索中文本的下一位是不确定的，所以以“abc”作为新的已经匹配的字符串是完全合理的。

由于在KMP算法中前缀的定义为严格前缀，因此，最终能够递归地完成匹配任务。

由上述描述，可以对KMP前缀函数进行更深入的研究。

现在假设有一特定模式P，且有一文本T，P有q个字符，可以用P[1，2，3…q]来表示。现在，已知P[1，2，…，y]与T[g+1，g+2，g+3，…，g+y]匹配（y < q），即P[1，2，…，y] = T[g+1，g+2，g+3，…，g+y]，那么满足P[1，2，…，x] = T[g`+1，g`+2，…，g`+x]的最小位移g`>g是多少？这里位移g+y = g`+x。此处的位移g`是大于g的未必非法的文本中的第一个位移，因为由于前缀匹配的关系，我们可以立马排除g+1，g+2，…，g`位，这些位会造成原匹配的下一位不匹配，而对于g`+1以后的位，我们则可以完全放心。

于是，从特定模式的角度来说，可以利用模式与其自身进行比较，以预先计算出需要的信息。由此，现在可以来正式的介绍前缀函数。还是以特定模式“abcabcde”来说明，假设前缀函数为h（i），i为第几个字符的位置，h（i）代表了第i位匹配而第i+1位不匹配时最大的匹配其本身的前缀字符数。例如，在“abcabcde”中，若已经匹配了“abcabc”，其后一位不匹配，可以看出，“abc”是匹配“abcabc”的最长的前缀，因此可以直接将模式向后移三位，即h（6） = 3，同时，可知h（1） = 0，因为光是一个“a”字符匹配并且下一位不匹配并不能说明什么，没有严格上的前缀子字符串可以使用，只能继续用“a”来与文本的下一个字符进行比较看是否匹配，同理，光是“ab”或者“abc”匹配也无法得到什么，因为当下一位不匹配时这两个字符串都得完全从“a”开始重新匹配，因此，h（1） = h（2） = h（3） = 0。在上个例子中，h（i）的全部数值如下：h（1） = h（2） = h（3） = 0，h（4） = 1，h（5） = 2，h（6） = 3，h（7） = 0。

KMP的前缀函数是整个KMP字符匹配算法的核心，当通过对特定模式的分析而得出前缀函数后，一切就手到擒来了，剩下的只是将特定模式与文本进行比较并使用这个前缀函数。

在与文本匹配时，一开始就像一般的比较字符一样，看开头是否相等，然后比较下一位，若最终整个模式，都被匹配，那则是很幸运的取得了开门红，可以继续比较文本的下一个词；倘若不是整个字符串都能匹配的上，那便可以利用前缀函数所透露的信息，将模式向后移动，直到移到最长的前缀被匹配，然后在比较下一位，相同则继续比较，否则再看前缀函数，再移动直到最长的前缀被匹配。

以上便是KMP字符匹配算法的所有步骤。

KMP这一算法经过无数能人志士的推导和检验，早已证明其是一个高效且易实现的算法，正如前文所述，其所用时间花销在m+n这一数量级上，是各种同类算法中耗时最少的。

下面，作者根据对KMP算法的分析，使用C语言对算法进行了实现。

2 KMP算法实现

根据上文的分析，作者首先写出了KMP算法的伪代码，其中，前缀函数为next（），P为特定模式，T为要匹配的文本，如下所示：

计算前缀函数：

以上便是KMP匹配算法的伪代码，其中，伪代码分为两部分，第一步首先先对特定模式进行分析，生成需要的前缀函数next（），然后第二步再使用生成的前缀函数来配合特定模式与文本进行匹配。

根据如上的分析，作者首先实现了生成前缀函数的C语言源代码：

以上便是使用C语言实现的KMP匹配算法。

可以看到，在程序中，作者首先用getnext（）函数生成得到前缀函数的对应于特定模式每一位的数值，然后在kmp（）函数中再使用特定模式的字符数组m[]和储存前缀函数相应位数值的next[]数组来对文本中的内容进行匹配查找过程，当获得一处匹配时便返回匹配处在文本中的位置，若整个文本没有内容能匹配特定模式，则kmp（）函数最终返回-1。

3 总结

本文探究分析了著名字符串匹配算法——KMP算法。在文中，作者分析了KMP算法的思想和原理，并通过简单的例子进行了演示，最后使用C语言对其进行了实现。

KMP算法可以说是字符串匹配算法中运行速度最快的算法之一，相对于同类别的RK算法和有限自动机算法，其速度有可观的提高，并且，KMP算法中充分利用已知信息的思想，也启发着日后算法的发展，相信在不久的将来，会有更高效的算法出现！

参考文献：

[1] Mark Allen Weiss.数据结构与算法分析[M].人民邮电出版社，2005.

[2] George F.Luger.Artificial intelligence.China Machine Press，2010.

[3] Robert Sedgewick算法.C语言实现[M].机械工业出版社，2009.

[4] Sedgewick，R& Wayne，K.算法[M].人民邮电出版社，2012.

[5] Kyle Loudon.算法精解[M].机械工业出版社，2012.