序列拼接中重复子串屏蔽的KMP算法

• 作者: 李小妹 王能超
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: KMP算法 失效函数 重复子序列
• 年，卷（期）: 2006,（2）
• 所属期刊栏目: 算法研究
• 页码范围: 308-311
• 页数: 4页
• 分类号: TP18
• 字数: 4267字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-1220.2006.02.029

摘要

在序列拼接中,为了解决重复序列这个难题,本文提出了利用KMP匹配算法来识别并屏蔽重复序列的方法.该方法利用模式序列中的失效函数计算得到失效链接值,也就是当前一位置匹配失败后,下一次匹配开始的位置.利用这一函数避免了可预见的无用搜索,将穷举搜索算法所需的计算量大大减少.通过计算机模拟,验证了对重复序列的屏蔽,该算法将穷举算法所需时间复杂度由原来的减少到了.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王能超	华中科技大学计算机科学与技术学院	58	640	17.0	23.0
2	李小妹	华中科技大学计算机科学与技术学院	14	76	6.0	8.0