%0 Journal Article
%T boyer-moore串匹配算法的改进
%A 韩光辉
%A 曾诚
%J 计算机应用
%D 2014
%X ？在分析boyer-moore(bm)算法的基础上，提出了bm算法的一个新的变形。其基本思想是在算法的预处理阶段，对扩展模式串pa建立好后缀规则，其中：p是模式串，a是字母表中的任一字符，既加大了已匹配后缀的长度，同时隐含了sunday算法的坏字符规则，从而获得更大的窗口跳跃距离。理论分析证明，该算法具有线性最差时间复杂度和亚线性平均时间复杂度，空间复杂度为o(m(σ+1))。实验结果表明，该算法的实际性能与bm算法相比有明显改善，尤其适合小字母表的情形。
%K 串匹配
%K bm算法
%K 复杂度分析
%U http://www.joca.cn/CN/abstract/abstract17122.shtml