基于KMP算法的改进算法KMPP

摘要：

KMP算法和BM算法是经典的单模式匹配算法,但KMP算法中文本指针i每次只能移动一个字符,整体的匹配效率并不高,结合KMP算法和BM算法的优点提出一种改进算法(KMPP).算法的思想是模式串与文本在j处不匹配时,预算出模式串移动next[j]后末字符在文本中的位置,当该位置的文本字符与末字符不匹配时,则用该字符进行坏字符匹配,这两步的跳跃距离就是文本指针i移动的距离,从而使指针i每次移动的距离达到最大.实验结果表明,该算法匹配次数远低于KMP算法的匹配次数,提高了模式匹配的效率.

关键词：模式匹配、KMP算法、BM算法、KMPP算法

所属期刊栏目：52

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金重大国际地区合作研究项目81320108019;福建省自然科学基金2014J01220

在线出版日期：2016-08-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：33-37