一种改进的BM字符串匹配算法

摘要：

　　经典字符串匹配算法的本质都是从左向右或者从右向左顺序进行字符匹配的，在主串中存在大量子串与模式串前缀或者后缀相同时效率较低，并且模式串最大右移长度为模式串长度。改进算法采用二分匹配字符串的方法，有效地避免了由主串中大量子串与模式串前缀相同或者后缀相同引起的无意义比较次数。模式串的移动距离根据改进的坏字符规则进行计算，增大了模式串的移动距离。实验结果表明，改进的字符串匹配算法可以有效地减少字符串的匹配次数和移动次数，达到了提高算法效率的目的。

关键词： 匹配 模式串 主串 算法

作者: 李韦男 虞慧群

作者单位: 华东理工大学 计算机应用技术系,上海市 中国 200237

会议类型: 国内会议

会议名称: 第十一届全国软件与应用学术会议(NASAC2012)

会议地点: 南京

会议语种:中文

页码: 1-7

在线出版日期: 2012-10-20（万方平台首次上网日期，不代表论文的发表时间）