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

李萍　赵润林

摘要：模式匹配是字符串的基本运算之一，也是数据结构课程的重点算法之一。在当今文本信息海量增长的时代，如何快速地定位就显得尤为重要。该文通过朴素模式匹配算法与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]，则模式串回滚到起始位置，而主串回滚到起始位置的下一个字符。如此一直循环直至主串结束或模式串结束。……