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

被引：26

作者：

鲁宏伟

魏凯

孔华锋

机构：

[1] 华中科技大学计算机科学与技术学院

来源：

华中科技大学学报(自然科学版) | 2006年 / 10期

关键词：

模式匹配; 算法; 模式串; 主串; 时间复杂度;

D O I：

10.13245/j.hust.2006.10.013

中图分类号：

TP391.4 [模式识别与装置];

学科分类号：

0811 ; 081101 ; 081104 ; 1405 ;

摘要：

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

引用

页码：41 / 43

页数：3