模式匹配算法的研究与实现

李萍　赵润林

摘要：模式匹配是字符串的基本运算之一，也是数据结构课程的重点算法之一。在当今文本信息海量增长的时代，如何快速地定位就显得尤为重要。该文通过朴素模式匹配算法与KMP算法的比较说明各自的优缺点，同时通过提高获取next数组的效率，加快KMP算法的匹配速率。

关键词：模式匹配；KMP；NEXT函数；文本搜索

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2017）18-0025-02

从计算机诞生至今，文本信息海量地增长，无论是在金融、航海、DNA检测、网络入侵等领域都需要在文本中快速地查找所需要的信息，因此设计出一个好模式匹配算法，不公可以高效地进行定位，还可以提高文本编辑能力，提高改善人类的生活。

模式匹配即子串的定位操作，是数据结构中逻辑结构为串的最重要操作之一。该算法的主要目的是找出特定的模式串在一个较长的字符串中出现的位置。如有两个字符串T称为模式串，字符串s称为主串，找出模式T在主S中的首次出现的位置。一旦模式T在目标s中找到，就称发生一次匹配。例如，目标串S=ababeabcaebab，模式串T=abcac，则匹配结果为6，其中经典的模式匹配算法包括朴素匹配算法、KMP。

1朴素模式匹配算法

朴素模式匹配算法的基本思想是在模式串T和主串S中，使用循环变量I，j，分别在模式串和主串中循环跑动，如果模式串与主串对应字符相等S[i]=T[j]，则同时后移；如果模式串与主串对应字符不相等S[i]≠[j]，则模式串回滚到起始位置，而主串回滚到起始位置的下一个字符。如此一直循环直至主串结束或模式串结束。朴素模式匹配算法的回溯演示如下：

算法流程图描述如下：

2 KMP算法

与朴素模式匹配算法比较，KMP算法最大的特点是模式串在匹配不相等的情况下，不再回溯，而是匹配串进行滑动，所以匹配串滑动的位置是算法的关键。由于模式串已匹配的字符串与主串已匹配内容相同，从模式串部分匹配字符中从前和从后数的字符串如果相同，即相同字符串无需再进行匹配，即模式串滑动的位置为相同字符数加1。滑动演示如下：

4总结

本文通过分析朴素匹配算法与KMP算法如何进行字符串比较，在比较相等与不相等时模式串与主串如何移动，说明两者的优缺点，并且在KMP算法中通过改進next函数值的计算，提高KMP匹配效率，并通过上机验证实现算法。endprint