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

刘传汉; 王永成; 刘德荣; 李党林

首页> 中文期刊> 《上海交通大学学报》 >基于混合策略的单模式匹配算法

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

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《上海交通大学学报》 |2007年第1期|36-41|共6页
作者
刘传汉; 王永成; 刘德荣; 李党林;
展开▼
作者单位

上海交通大学计算机科学与工程系;

展开▼
原文格式 PDF
正文语种 chi
中图分类理论、方法;
关键词
模式匹配; LDM算法; 后缀自动机; 有限状态自动机; 时间复杂度;

相似文献

中文文献
外文文献
专利

1. 基于遗传算法和禁忌搜索算法的混合策略及其应用 [J] . 孙艳丰 . 北京工业大学学报 . 2006,第003期
2. 一种基于Aho-Corasick算法改进的多模式匹配算法 [J] . CHEN Yongjie ,Wushour Silamu ,YU Qing . 现代电子技术 . 2019,第004期
3. 基于KR－BM算法的多模式匹配算法改进 [J] . 杨品 ,吴宇佳 ,刘嘉勇 . 信息安全与通信保密 . 2014,第011期
4. 基于Sunday算法的改良单模式匹配算法 [J] . 朱永强 ,秦志光 ,江雪 . 计算机应用 . 2014,第001期
5. 基于BF算法改进的字符串模式匹配算法 [J] . 蔡恒 ,张帅 . 电脑编程技巧与维护 . 2014,第022期
6. 基于内点法和遗传算法的地区电网无功优化混合策略 [C] . 樊小瑜 . 中国高等学校电力系统及其自动化专业第二十五届学术年会 . 2009
7. 单转子空调压缩机基于模式匹配追踪的转速波动抵制方法研究 [A] . 蒋铁钢 . 2020

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

摘要

著录项

相似文献

相关主题

期刊订阅