数据结构中模式匹配算法的教学方法探讨

任平红+陈矗

摘要：字符串是计算机处理文本编辑问题时经常使用的数据结构，其模式匹配算法是最常见的操作之一。常用的模式匹配算法有BF（Brute-Force）算法和KMP（Knuth-Morris-Pratt）算法。BF算法因匹配失败时主串和模式串都回溯，在某些情况下效率较差。KMP算法经优化后目标串无回溯，效率较高。文中分析了BF算法和KMP算法的教学方法，对于模式匹配的学习有一定的借鉴作用。

关键词：模式匹配；BF算法；KMP算法；next函数

中图分类号：G642 文献标识码：A 文章编号：1009-3044（2017）27-0173-02

1 概述

字符串是比较常用的特殊的线性结构，元素类型限定为字符。在实际的工作中，字符串常被用来处理非数值问题。字符串的模式匹配是很常见的问题，例如文本编辑中的查找等操作。一般的模式匹配是确定模式串T在目标串S中第一次完整出现的位置。常见的算法有朴素的BF算法和经优化以后的KMP算法。在教学过程中，由于BF算法思想简单，学生理解起来比较容易，教学效果较好。但是KMP算法思想较为复杂，部分学生对KMP算法的理解不够深刻，特别是对其理论推导过程认识模糊，对于模式匹配函数next的计算掌握的不牢固。针对以上问题，笔者结合多年的教学经验，对两种模式匹配算法的教学方法进行了分析和总结，对于教学有一定的借鉴作用。

2 BF算法

2.1 基本思想

BF算法被称为简单的、朴素的模式匹配算法。目标串S和模式T都从第1个字符开始匹配，如果成功则继续匹配下一个字符；如果匹配失败，则开始新的一趟匹配，目标串回到匹配失败这一趟开始位置的下一个位置，模式重新回到第1个字符。即如果S[i]和T[j]匹配失败，则i=i-j+1，而j=0（采用顺序结构存储字符串）。例如，某一趟匹配失败时，字符串S[i-j]…S[i-1]=T[0]…T[j-1]，但是S[i]与T[j]不相等。此趟匹配方串从i-j开始，所以下一趟从i-j+1开始，模式指针j=0。

2.2 算法

2.3 效率分析

BF算法简单明了，应用比较广泛。如果目标串的长度为n，模式串的长度为m。最好情况为每趟匹配失败都发生在模式的第一个字符。最好情况和平均情况下的时间复杂度均为O（m+n）。但是如果每趟匹配失败都发生在模式的最后一个字符上，效率较差，时间复杂度为O（mn）。其原因在于匹配的过程中目标串和模式的指针都回溯，各趟匹配之间是孤立的，下一趟匹配没有充分利用前面部分匹配的结果。KMP算法为BF算法的改进算法。

3 KMP算法

3.1 基本思想

KMP算法对BF算法做了很大的改进。其出发点在于当匹配失败，要开始新的一趟匹配时，目标串指针不回溯，而模式向右滑动一段距离，其实是模式指针回溯。要实现此目标，必须利用已有的部分匹配的结果。在教学过程中，除了利用实例说明问题外，还需要将其理论的推导公式向同学们讲解清楚，这样才能使学生真正理解KMP算法的精髓。KMP算法的核心在于如何确定模式向右滑动的距离值k。模式T的每个位置匹配失败时对应的k值称为next函数，用一维数组next[]表示。

3.2 理论推导

得到模式T的next函数之后，KMP算法的匹配过程和BF算法类似，不同之处在于当匹配失败时，主串的指针i不变，模式的指针j回到next[j]的位置上，从而实现了模式不回溯的目标。

3.4 分析

与BF算法相比，KMP算法的先进之处在于目标串指针在匹配失败时是不回溯的。虽然其平均的时间复杂度为O（n+m），但需要事先计算模式的next函数，并且算法的难度明显增加，理解起来比较复杂。

4 总结

BF算法和KMP算法是字符串模式匹配的两个重要算法。因BF算法的思想简单，理解起来比较容易，学生一般对其掌握的较好。KMP算法对BF算法做了较大的改进。当匹配失败时，目标串指针不回溯，模式指针向右滑动一段距离，而滑动距离的大小由模式自身决定，与目标串无关。KMP算法充分利用了已有的部分匹配的结果以及模式本身的特点，效率较高。但是其算法较为复杂，模式的next函数的计算以及匹配的过程都需要学生熟练掌握和应用。即使如此，KMP算法的思想也非常值得借鉴，在教学过程中，需要将其理论推导过程向学生进行深入而透彻的讲解。同时结合具体的实例，向学生清楚明了地演示其匹配过程，从而达到较好的教学效果。

参考文献：

[1] 王红梅，胡明，王涛.数据结构（C++版第2版）[M].北京：清华大学出版社，2011：81-85.

[2] 安杨，赵波.模式匹配算法的教学探讨[C].第24届全国计算机新科技与计算機教育学术会议论文集，2013：121-125.

[3] 李萍，赵润林.模式匹配算法的研究与实现[J].电脑知识与技术，2017，13（18）：25-26.endprint