%0 Journal Article %A 韩光辉 曾诚 %T Boyer-Moore串匹配算法的改进 %D 2014 %R 10.11772/j.issn.1001-9081.2014.03.0865 %J 计算机应用 %P 865-868 %V 34 %N 3 %X

在分析Boyer-Moore (BM)算法的基础上,提出了BM算法的一个新的变形。其基本思想是在算法的预处理阶段,对扩展模式串Pa建立好后缀规则,其中:P是模式串,a是字母表中的任一字符,既加大了已匹配后缀的长度,同时隐含了Sunday算法的坏字符规则,从而获得更大的窗口跳跃距离。理论分析证明,该算法具有线性最差时间复杂度和亚线性平均时间复杂度,空间复杂度为O(m(σ+1))。实验结果表明,该算法的实际性能与BM算法相比有明显改善,尤其适合小字母表的情形。

%U http://www.joca.cn/CN/10.11772/j.issn.1001-9081.2014.03.0865