BM模式匹配算法剖析

被引：45

作者：

巫喜红 ^{[1
]}

凌捷 ^{[2
]}

机构：

[1] 嘉应学院计算机科学与技术系

[2] 广东工业大学计算机学院

来源：

计算机工程与设计 | 2007年 / 01期

关键词：

BF算法; KMP算法; BM算法; 模式匹配; 时间复杂度;

D O I：

10.16208/j.issn1000-7024.2007.01.010

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

在对典型的BF、KMP模式匹配算法进行比较分析的基础上,详细分析了BM算法。为了进一步加快算法的速度,对BM算法中已经部分匹配的移动位置情况进行改进。在原有的移动距离函数基础上增加一个新的移动距离函数,从而尽量利用已有信息进行更大的尝试位置移动,使算法具有更高的效率。通过引用具体实例,比较分析了改进前后的BM算法,结果证明改进后的BM算法的速度更快,效率更高。

引用

页码：29 / 31

页数：3

共 8 条

[1]

IDS中新的快速多模式匹配算法及其设计 [J].