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

Improvement of Boyer-Moore String Matching Algorithm

作　　者：贺龙涛[1] 方滨兴[2] 胡铭曾[1] 

机构地区：[1]哈尔滨工业大学,国家计算机信息内容安全重点实验室,黑龙江哈尔滨150001 [2]国家计算机网络与信息安全管理中心,北京100031

出　　处：《计算机应用》2003年第3期6-8,12,共4页journal of Computer Applications

基　　金：国家 8 63计划项目(863-104-02-01)

摘　　要：在对著名的Boyer -Moore串匹配算法进行分析后 ,对BM算法中的尝试位置移动处理部分进行改进 ,提出了IBM算法。该算法将好后缀移动与坏字符移动合并进行处理 ,从而尽量利用已有信息进行更大的尝试位置移动 ,使算法具有更高的效率。对IBM算法进行复杂度分析 ,对BM算法、KMP算法和IBM算法进行实际性能比较 ,结果表明IBM算法的平均运行时间明显优于BM算法与KMP算法。String matching is an essential and important problem in computer science. After BM algorithm is analyzed, the shift function of the attempt position in BM algorithm is improved, and IBM algorithm is put forward. The IBM algorithm combines Good Suffix Shift and Bad Character Shift to process, and makes the most of known information to increase the shift distance so that it is more efficient. In the end, the analysis of the complexity of IBM algorithm and the comparison of performance in practice about KMP, BM and IBM algorithms are carried out. The results show that the average running time of IBM algorithm is 58% of BM algorithms, and the average comparing time of IBM algorithm are 52% of BM algorithms.

关 键 词：BM串匹配算法 KMP算法 IBM算法 计算机 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]