基于混合策略的单模式匹配算法

• 作者: 刘传汉 刘德荣 李党林 王永成
• 来源期刊: 上海交通大学学报
• 学科: 工学
• 关键词: 模式匹配 LDM算法 后缀自动机 有限状态自动机 时间复杂度
• 年，卷（期）: 2007,（1）
• 所属期刊栏目: 自动化技术、计算机技术
• 页码范围: 36-41
• 页数: 6页
• 分类号: TP301
• 字数: 5118字
• 语种: 中文
• DOI: 10.3321/j.issn:1006-2467.2007.01.009

摘要

结合后缀有限自动机和正向有限自动机的优点,提出了两个单模式匹配算法.算法中,无论是后缀自动机还是正向有限自动机,只要扫描到的模式前缀长度R＞O或者超过模式长度的1/2时,使用正向有限自动机继续向右进行扫描;否则都滑动m-R个字符,使用后缀自动机反向扫描模式串的前缀.两个算法的最差、最好时间复杂度分别为O(n)和O(n/m).结果表明,在短模式的情况下,两个算法的平均时间复杂度均好于RF和LDM,在小字符集长模式或大字符集短模式的情况下它们的平均性能好于BM.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王永成	上海交通大学计算机科学与工程系	94	2540	28.0	48.0
2	刘传汉	上海交通大学计算机科学与工程系	12	138	6.0	11.0
3	刘德荣	上海交通大学计算机科学与工程系	6	47	4.0	6.0
4	李党林	上海交通大学计算机科学与工程系	2	5	1.0	2.0