基于KMP算法的改进算法KMPP

• 作者: 李莉 林劼 江秉华 江育娥
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 模式匹配 KMP算法 BM算法 KMPP算法
• 年，卷（期）: 2016,（8）
• 所属期刊栏目: 理论与研发
• 页码范围: 33-37
• 页数: 5页
• 分类号: TP311
• 字数: 4007字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1405-0426

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李莉	福建师范大学软件学院	47	104	5.0	7.0
2	林劼	福建师范大学软件学院	25	138	6.0	11.0
3	江育娥	福建师范大学软件学院	11	65	4.0	8.0
4	江秉华	南京医科大学病理系	2	14	1.0	2.0