改进的多模式字符串匹配算法

摘要：

在经典的AC多模式字符串匹配算法的基础上,结合BMH算法的优点,提出了一种快速的多模式字符串匹配算法.一般情况下,该算法不需要匹配目标文本串中的每个字符,而是在实际比较之前跳过尽可能多的字符,以减少字符比较的操作,实现快速匹配.在模式串较长和较短的情况下,算法都有很好的性能.实验表明,在模式串较短时,本算法所需的时间仅为AC算法的50%～30%;在模式串较长时,所需时间为AC算法的26.7%～15.2%.

关键词：字符串匹配、AC算法、BMH算法、多模式匹配、算法复杂度

所属期刊栏目：27

分类号：TP18(自动化基础理论)

资助基金：国防科技应用基础研究基金C2720061361;国家高技术研究发展计划863计划2005AA147030

在线出版日期：2007-07-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：1415-1417