字符串模式匹配算法的改进

• 作者: 张国平 徐汶东
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: KMP算法 BM算法 入侵检测 模式匹配 移动距离
• 年，卷（期）: 2007,（20）
• 所属期刊栏目: 安全与保密技术
• 页码范围: 4881-4884
• 页数: 4页
• 分类号: TP393.08
• 字数: 3448字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-7024.2007.20.018

摘要

字符串模式匹配算法是入侵检测系统中的一种重要算法.通过对两种著名的匹配算法KMP和BM算法以及现有的各种改进算法的分析,提出一种简单实用、易于理解的字符串匹配改进算法.该算法通过每次匹配失败时特殊位置上字符的启发来获得字符串向后移动的可能距离,这个距离由定义的一个统一函数求出,取其中的最大值作为字符串向后移动的实际距离.实验结果表明,该算法能减少模式匹配中字符的比较次数和尝试次数,提高模式匹配的效率.