分块法的模式匹配算法的研究

摘要：

为提高模式匹配算法性能,介绍经典的模式匹配算法Byoer-Moore和Sunday,分析它们改进后的效率,根据分块法的特点,提出一种新的分块模式匹配(block pattern matching,BPM)算法.BPM算法在预处理阶段先确定模式串的首字符在文本串的位置,再确定此字符后长度等于模式串长度的字符是否等于模式串的尾字符,若符合条件,采用单链表存储结构进行存储,在匹配阶段,利用单链表信息进行双向匹配.实验结果表明,BPM算法大大减少了匹配次数和字符比较个数,从而提高匹配效率.

关键词：分块法、模式匹配、分块模式匹配(BPM)算法、BM算法、Sunday算法

所属期刊栏目：26

分类号：TP393(计算技术、计算机技术)

资助基金：广东省科技创新项目2012KJCX0097The Science and Technology Innovation Project of Guangdong Province2012KJCX0097

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

页数：共5页

页码：551-555