-
题名基于KMP算法的改进算法KMPP
被引量：14
- 1
-
-
作者
李莉
江育娥
林劼
江秉华
-
机构
福建师范大学软件学院
南京医科大学病理系
-
出处
《计算机工程与应用》
CSCD
北大核心
2016年第8期33-37,共5页
-
基金
国家自然科学基金重大国际(地区)合作研究项目(No.81320108019)
福建省自然科学基金(No.2014J01220)
-
文摘
KMP算法和BM算法是经典的单模式匹配算法,但KMP算法中文本指针i每次只能移动一个字符,整体的匹配效率并不高,结合KMP算法和BM算法的优点提出一种改进算法(KMPP)。算法的思想是模式串与文本在j处不匹配时,预算出模式串移动next[j]后末字符在文本中的位置,当该位置的文本字符与末字符不匹配时,则用该字符进行坏字符匹配,这两步的跳跃距离就是文本指针i移动的距离,从而使指针i每次移动的距离达到最大。实验结果表明,该算法匹配次数远低于KMP算法的匹配次数,提高了模式匹配的效率。
-
关键词
模式匹配
KMP算法
BM算法
kmpp算法
-
Keywords
pattern matching
KMP algorithm
BM algorithm
kmpp algorithm
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
