一种改进的KMP高效模式匹配算法

• 作者: 孔华锋 魏凯 鲁宏伟
• 来源期刊: 华中科技大学学报（自然科学版）
• 学科: 工学
• 关键词: 模式匹配 算法 模式串 主串 时间复杂度
• 年，卷（期）: 2006,（10）
• 页码范围: 41-43
• 页数: 3页
• 分类号: TP391.4
• 字数: 2512字
• 语种: 中文
• DOI: 10.3321/j.issn:1671-4512.2006.10.013

摘要

针对KMP算法存在着主串与模式串中多个相同字符重复比较的缺陷,在KMP算法的基础上,给出了一种新的模式匹配算法,该算法不像KMP算法那样向左滑动模式串的指针,而是每次比较字符不匹配时,根据模式串当前字符的特征值k,使主串的指针向前跳跃k个值,且使模式串的指针置于起始位置,开始新一轮的匹配,加快了主串的匹配速度.理论分析和试验证明,该算法需要的比较次数比KMP算法减少将近一半.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	鲁宏伟	华中科技大学计算机科学与技术学院	53	548	12.0	22.0
2	孔华锋	华中科技大学计算机科学与技术学院	15	160	6.0	12.0
3	魏凯	华中科技大学计算机科学与技术学院	3	53	1.0	3.0