一种快速的多模式字符串匹配算法

被引：73

作者：

许一震

王永成

沈洲

机构：

[1] 上海交通大学计算机科学与工程系,上海交通大学计算机科学与工程系,上海交通大学计算机科学与工程系上海,上海,上海

来源：

上海交通大学学报 | 2002年 / 04期

关键词：

匹配; 有限自动机; 多模式匹配;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

080201 [机械制造及其自动化];

摘要：

以基于有限自动机的多模式匹配算法 (DFSA)为基础 ,结合 Boyer- Moore(BM)和 QuickSearch (QS)快速单模式匹配算法的优点 ,提出了一种快速的多模式字符串匹配算法 .在一般情况下 ,该算法不需要匹配目标文本串中的每个字符 ,能充分利用匹配过程中本次匹配不成功的信息和已经匹配成功的信息 ,跳过尽可能多的字符 .实验表明 ,模式串较短时 ,本算法所需时间为 DFSA算法的 1 /2～ 1 /3 ;模式串较长时 ,其所需时间为 DFSA算法的 1 /3～ 1 /5

引用

页码：516 / 520

页数：5