Release Time:2019-03-10  Hits:

Indexed by: Journal Article

Date of Publication: 2013-12-15

Journal: 计算机研究与发展

Included Journals: Scopus、CSCD、ISTIC、PKU、EI

Volume: 50

Issue: 12

Page Number: 2699-2706

ISSN: 1000-1239

Key Words: 串匹配;多模式;自动机;失败函数;高级AC

Abstract: 高级AC(advanced AC,AAC)是一种基于自动机的多模式串匹配算法,应用极为广泛.在大规模匹配时AAC自动机构建耗时较大,改进了经典精确单模式匹配算法——DFA算法自动机构建过程,并将其扩展到多模式匹配领域,提出Set DFA自动机,并证明Set DFA自动机和AAC自动机一致.该自动机构建方法简单清晰,无需计算失败函数,自动机内每个状态在生成后只需访问一次即可完成自动机构建.实验表明Set DFA构建时间只有AAC自动机的一半左右.