浅论《数据结构》中KMP模式匹配算法讲解

杨凌雪 田宏兵

摘 ?要：模式匹配是《数据结构》中关于字符串的一个基本运算，一般有两种方法，分别为“朴素算法”与“KMP算法”。KMP算法是一种高效的字符匹配算法，它的关键在于当字符匹配失败以后，利用next数组中的信息使指针不需要回退，这样就减少了匹配的次数，提高效率。KMP算法不容易理解，该文通过举例等方法分析KMP算法的匹配原理及过程。

关键词：模式匹配 ?next数组 ?KMP算法讲解

中图分类号：TP311.12-4 ? 文献标识码：A 文章编号：1672-3791（2019）07（a）-0196-03

Abstract： Pattern matching is a basic operation on strings in Data Structure. There are generally two methods， namely "simple algorithm" and "KMP algorithm". The KMP algorithm is an efficient character matching algorithm. The key is that the information in the next array is used to make the pointer don't need to be rolled back when the character matching fails， thus reducing the number of matching and improving efficiency. The KMP algorithm is not easy to understand. This paper analyzes the matching principle and process of KMP algorithm by examples.

Key Words： Pattern matching; Next array; KMP algorithm explanation

字符串的模式匹配，即找寻字符串p第一次出现在字符串t中的起始位置。计算机科学研究最广泛，最古老的问题之一就是字符串匹配。关于字符串的模式匹配，《数据结构》教材中一般介绍两种方法：一是“朴素的模式匹配算法”，另外一个是“快速模式匹配算法”，也就是KMP算法[1]。在教学过程中，KMP算法不易理解，特别是关于next数组的计算和作用部分，如果没有合适的理论推导方法及例子，教师在讲解的过程中会感觉事倍功半。因此，该文讨论如何讲好KMP算法。

1 ?朴素模式匹配算法

朴素的模式匹配算法的基本思想是：逐个使用p中的字符去与t中的字符进行比较，如图1所示。

其中正文t的长度用n表示，模式字符串p的长度用m表示。如果t1=p1，t2=p2，…，tm=pm，则模式匹配成功，p1p2…pm即为所要寻找的子串，此时返回其起始位置1即可;否则，将p向右移动一个字符，然后用p中的字符从头开始与t里面对应的字符一一比较[2]，如图2所示。

重复此操作直到匹配成功，或p已移动到这样一个位置：t中剩余字符数小于p长度，那么就表明模式匹配不成功，t中没有子串与p相等，我们约定返回-1。

朴素模式匹配算法理解起来简单，算法也易于实现，但因其执行效率低，最坏情况下时间复杂度为O（nm）。分析该算法我们知道，效率低的原因在于，寻求匹配时，没有充分利用部分匹配的结果，每次比较不匹配时，模式p总是只能向右移动一个字符的位置，存在大量回溯。

2 ?KMP算法

在进行字符串比较时，能否在匹配不成功时不从头开始匹配？部分匹配的信息可否记录下来加以使用？要求不回溯，模式就需要向右滑动一段距离，那么又如何确定滑动多远的距离呢？

KMP算法解决了上述问题。

2.1 next数组

next[j]指p[j]字符前有多少个字符与p开头的字符相同。KMP算法中，模式p部分匹配的信息记录在next数组中，因此next数组确定了模式p向右滑动的距离。教学过程中，next数组的定义、作用、数组元素的获取和使用方法是字符串模式匹配章节讲述的关键。

先看如下式子。

模式串p存在某个k（0<><>

那么next[j]=k。

例如：

模式p=abcabcd，j=6时，p0p1p2=p3p4p5，说明p[6]前面有3个字符与模式开头的3个字符相同，所以有next[6]=3。

归纳一下，next[j]数组定义如下：

现举例说明。

p=ababaaabab，next[j]数组为表1所示。

我们规定，next[0]=-1，next[1]=0（因p[1]前只有一个字符）。p[2]前的字符b和p开头的字符a不同，故next[2]=0。p[3]前的字符a和p开头的字符a相同，故next[3]=1。p[4]前的字符ab和p开头的字符ab相同，故next[4]=2。p[5]前的字符aba和p开头的字符aba相同，故next[5]=3。p[6]前只有一个字符a和p开头的字符a相同，故next[6]=1。以此類推。

明白了next数组的含义，再来讲解根据模式p求数组next值的程序，就容易理解了。求next数组的程序如下：

void getnext（seqstring p，int next[]）

{ ?int ?i ，j;

编辑整理：科学技术创新杂志社编辑部 官方网站：www.hljkxzzs.com