一种时间复杂度最优的精确串匹配算法

• 作者: 余翔湛 方滨兴 贺龙涛
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 后缀自动机 有限状态自动机 LDM算法 串匹配 复杂度分析
• 年，卷（期）: 2005,（5）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 676-683
• 页数: 8页
• 分类号: TP301
• 字数: 5121字
• 语种: 中文

摘要

现有的串匹配算法通常以模式长度作为滑动窗口大小.在窗口移动后,往往会丢弃掉一些已扫描正文的信息.提出了LDM(linear DAWG matching)串匹配算法,该算法将正文分为[n/m]个相互重叠、大小为2m-1的扫描窗口.在每个扫描窗口内,算法批量地尝试m个可能位置,首先使用反向后缀自动机从窗口中间位置向前扫描模式前缀;若成功,则再使用正向有限状态自动机从中间位置向后扫描剩余的模式后缀.分析证明,LDM算法的最差、最好、平均时间复杂度分别达到了理论最好结果:O(n),O(n/m),O(n(1ogσm)/m).实际性能测试也验证了平均时间复杂度最优这一理论结果.而且,对于在较大字母表下查找短模式的情况,LDM算法速度在被测试算法中最快.总之,LDM算法不但适合进行离线模式匹配,而且还特别适合需要进行在线高速匹配的应用.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	方滨兴	哈尔滨工业大学计算机网络与信息安全技术研究中心	175	3885	33.0	56.0
2	余翔湛	哈尔滨工业大学计算机网络与信息安全技术研究中心	44	576	14.0	23.0
3	贺龙涛	哈尔滨工业大学计算机网络与信息安全技术研究中心	8	266	8.0	8.0