计算机应用 ›› 2014, Vol. 34 ›› Issue (3): 865-868.DOI: 10.11772/j.issn.1001-9081.2014.03.0865
韩光辉1,曾诚2
HAN Guanghui1,ZENG Cheng2
摘要:
在分析Boyer-Moore (BM)算法的基础上,提出了BM算法的一个新的变形。其基本思想是在算法的预处理阶段,对扩展模式串Pa建立好后缀规则,其中:P是模式串,a是字母表中的任一字符,既加大了已匹配后缀的长度,同时隐含了Sunday算法的坏字符规则,从而获得更大的窗口跳跃距离。理论分析证明,该算法具有线性最差时间复杂度和亚线性平均时间复杂度,空间复杂度为O(m(σ+1))。实验结果表明,该算法的实际性能与BM算法相比有明显改善,尤其适合小字母表的情形。
中图分类号: