4.3.2　KMP算法

D.E.Knuth（克努特）、J.H.Morris（莫里斯）和V.R.Pratt（普拉特）三个人同时提出了模式匹配的改进算法，称为Knuth－Morris－Pratt算法，简称为KMP算法。该算法相比Brute－Force算法在算法的执行效率上要高。

为什么这么说呢，通过分析图4－3所示的匹配过程，可以得出造成Brute－Force算法效率低的原因在于回溯，即在某趟匹配失败后，主串指针i要回到本趟比较的首字符的下一个字符位置，模式串指针j要回到首字符位置，然后进行新一趟的匹配。然而，这些回溯并非是必要的。在图4－3中，主串S＝“s0s1s2s3s4s5”＝“cddcdc”，模式串T＝“t0t1t2”＝“cdc”，当第一次匹配失败后，下一次的比较位置为i＝1和j＝0，即比较s1和t0。而t0≠t1（即c≠d），s1＝t1，推导出s1≠t0，则比较s1和t0无意义。同理，t0≠t2（即c≠d），s2＝t2，推导出s2≠t0，则比较s2和t0无意义。因此，可直接比较s3和t1，则此时i不需要回溯，而j向右“滑动”一个字符，这应该是第四次匹配过程。这样第四次匹配就充分利用了前几次匹配的信息。

从以上分析可以看到，当si与tj比较不相等时，主串指针i不必回溯，模式串指针j向右“滑动”到k位置（0≤k＜j），直接比较si与tk。那么现在的关键问题就是如何确定k值。答案是使用一个next［j］函数。

在模式串中，每一个tj都有一个k值对应，这个k值仅与模式串本身有关，而与主串S无关。一般用next［j］函数来表示tj对应的k值。

当模式串T＝“t0t1…tk…tj－ktj－k＋1…tj－1tj”中存在“t0t1…tk－1”＝“tj－ktj－k＋1…tj－1”时，称等式左边式子为模式前缀，等式右边式子为模式后缀。

若在某一趟比较中出现以下情形：

它相当于：

则下一趟匹配时，模式前缀不必再比较了，因为上一趟匹配时已经比较了模式后缀，而模式后缀和模式前缀相等。因此，在下一趟匹配时，应把模式串指针j向右“滑动”到k位置，直接比较si和tk即可。

通过以上分析，不难得出这个tj对应的k值即next［j］函数的求法。

下面我们先给出一个next［j］函数的定义。

其中，max｛k｜0＜k＜j且“t0t1…tk－1”＝“tj－ktj－k＋1…tj－1”｝表明模式串中存在t0t1…tk－1和tj－ktj－k＋1…tj－1两个相等的子串，且这两个子串是所有相等子串中长度最长的。

下面讨论求next［j］函数值问题。从next［j］函数可以得出，求解next［j］函数值的过程就是一个递推的过程。

初始时：

若存在next［j］＝k，即模式串T中存在

k为满足等式的最大值，则计算next［j＋1］的值存在以下两种情况。

①若tk＝tj，则表明在模式串T中存在

且不可能存在另一个k'（k'＞k），因此可以得到

②若tk≠tj，则表明在模式串T中存在

此时，可以把计算next［j］函数值的问题看成是另一个模式匹配过程。而整个模式串既是主串又是模式串，如图4－4所示。

图4－4 求next［j＋1］

之前在匹配过程中，当tk≠tj时，应将模式串T'向右滑动至k'＝next［k］，并把k'位置上的字符与“主串”T中j位置上的字符作比较。

若tk'＝tj，则表明在“主串”T中第j＋1个字符之前存在一个最大长度为k'的子串，使t0t1…tk'－1tk'”＝“tj－k'tj－k'＋1…tj－1tj（0＜k'＜k＜j）成立，因此有next［j＋1］＝k'＋1＝next［k］＋1。

若tk'≠tj，则将模式串T'向右滑动至k＂＝next［k'］后继续匹配。依此类推，直至tj和模式T'中的某个字符匹配成功或不存在任何k'（0＜k'＜k＜j）满足next［j＋1］＝k'＋1＝next［k］＋1，此时有next［j＋1］＝0。

综上所述，next［j］函数的求解方法是：模式串的第一个字符的next［j］函数值为0，第二个字符的next［j］函数值为1。求解其后字符的next［j］函数值时，应根据该字符的前一个字符进行比较。首先将ch（该字符的前一个字符）与其next［j］函数值所指位置上的字符进行比较，如果相等，则该字符的next［j］函数值就是ch的next［j］函数值加1；如果不等，向前继续寻找next［j］函数值所指字符的next［j］函数值，把该函数值所指字符与ch′（该字符的前一个字符）进行比较，直到找到某个字符的next［j］函数值所指的字符与ch′相等为止，则这个next［j］函数值加上1即为所求的next［j］函数值；如果向前一直找到第一个字符都没有找到相等的字符，则next［j］函数值为1。

上述定义的next［j］函数在某些情况下还存在缺陷。例如模式串T＝“aaaab”在和主串S＝“aaabaaaab”匹配时，当i＝4，j＝4时s4≠t4，由next［j］指示还需进行i＝4、j＝3，i＝4、j＝2，i＝4、j＝1三次比较。实际上，因为模式串中第1、2、3个字符和第4个字符都相等，因此不需要再和主串中第4个字符相比较，而可以将模式向右滑动4个字符的位置直接进行i＝5、j＝1时的字符比较。这就是说，若按上述定义得到next［j］＝k，而模式中tj＝tk，则当主串中字符si和tj比较不等时，无须再和tk进行比较，而直接和tnext［k］进行比较，也就是说，此时的next［j］应该和next［k］相同。因此，我们又可以得到修正后的next［j］函数为nextval［j］。

下面我们分别给出求next［j］函数值、求nextval［j］函数值及运用next值求解模式匹配的KMP算法的C语言算法实现。

1.求next［j］函数值的算法

算法4.2 求next［j］函数值

2.求nextval［j］函数值的算法

算法4.3 求nextval［j］函数值

3.KMP算法

算法4.4 KMP算法

下面我们通过一个实例看看如何求解next［j］和nextval［j］函数值，以及通过求解出的next值进行KMP算法的模式匹配。

例4.3 求模式串T＝“cbacb”的next［j］和nextval［j］函数值。

解：求解过程如表4－1所示。

表4－1 模式串T＝“cbacb”的next［j］和nextval［j］函数值

例4.4 在主串S＝“cbaccbacbbb”中用例4.3中求出的模式串T的next［j］函数值给出KMP算法的匹配过程。

解：

最后，我们简单分析一下KMP算法的时间复杂度。求next［j］函数值的算法的时间复杂度为O（m），而整个KMP算法的时间复杂度为O（n＋m）。通常，模式串的长度m比主串的长度n要小得多，因此，对整个匹配算法来说，所增加的这点时间是值得的。

虽然Brute－Force算法的时间复杂度是O（n×m），但在一般情况下，其实际的执行时间近似于O（n＋m），因此至今仍被采用。KMP算法仅当模式串与主串之间存在许多“部分匹配”的情况下才显得比前一种算法快得多。但是KMP算法的最大特点是指示主串的指针无须回溯，整个匹配过程中，对主串仅需从头至尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边读边匹配，无须回头重读。