Boyer-Moore串匹配算法的改进

韩光辉; 曾诚

首页> 中文期刊> 《计算机应用》 >Boyer-Moore串匹配算法的改进

Boyer-Moore串匹配算法的改进

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《计算机应用》 |2014年第3期|865-868|共4页
作者
韩光辉; 曾诚;
展开▼
作者单位

武汉商学院信息工程系;

武汉430056;

湖北大学数学与计算机科学学院;

武汉430062;

展开▼
原文格式 PDF
正文语种 chi
中图分类算法理论;
关键词
串匹配; BM算法; 复杂度分析;

相似文献

中文文献
外文文献
专利

1. 一种串匹配的快速Boyer-Moore算法 [J] . 李雪梅 ,代六玲 ,童新海 . 计算机应用研究 . 2005,第009期
2. 一种改进Boyer-Moore算法效率的预处理算法 [J] . 金人超 ,宋恩民 . 华中科技大学学报：自然科学版 . 2005,第z1期
3. 一种改进的Boyer-Moore算法在IDS中的应用 [J] . 王淅娜 ,喻建鹏 . 计算机科学 . 2013,第0z2期
4. BM串匹配算法与改进算法的研究 [J] . 王锋 . 福建电脑 . 2010,第007期
5. BM串匹配算法的一个改进算法 [J] . 王建国 ,郑家恒 . 计算机工程与科学 . 2007,第005期
6. 一种改进的BM字符串匹配算法 [C] . Li Weinan ,李韦男 ,Yu Huiqun . 第十一届全国软件与应用学术会议（NASAC2012） . 2012
7. 改进Boyer-Moore算法研究与应用 [A] . 夏玄一 . 2016

Boyer-Moore串匹配算法的改进

摘要

著录项

相似文献

相关主题

期刊订阅