对BM串匹配算法的一个改进

被引：10

作者：

贺龙涛

方滨兴

胡铭曾

机构：

[1] 哈尔滨工业大学国家计算机信息内容安全重点实验室

[2] 国家计算机网络与信息安全管理中心

[3] 哈尔滨工业大学国家计算机信息内容安全重点实验室黑龙江哈尔滨

[4] 北京

[5] 黑龙江哈尔滨

来源：

计算机应用 | 2003年 / 03期

关键词：

串匹配; BM算法; KMP算法; IBM算法; 尝试;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

在对著名的Boyer -Moore串匹配算法进行分析后 ,对BM算法中的尝试位置移动处理部分进行改进 ,提出了IBM算法。该算法将好后缀移动与坏字符移动合并进行处理 ,从而尽量利用已有信息进行更大的尝试位置移动 ,使算法具有更高的效率。对IBM算法进行复杂度分析 ,对BM算法、KMP算法和IBM算法进行实际性能比较 ,结果表明IBM算法的平均运行时间明显优于BM算法与KMP算法。

引用

页码：6 / 8+12 +12

页数：4