两种基于双向比较的最长公共子串算法

• 作者: 付云生 孔思淇 潘泽友 王开云 赵强 马卫东
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 最长公共子串 双向比较 连续同值区间 跨越 亚线性
• 年，卷（期）: 2013,（11）
• 所属期刊栏目: 软件技术
• 页码范围: 2444-2454
• 页数: 11页
• 分类号: TP301.6
• 字数: 5444字
• 语种: 中文

摘要

查找两个给定字符串的最长公共子串(LCSstr)是一类重要字符串分析问题,在字符串近似匹配、计算机病毒特征码对比等方面有着广泛的用途.最长公共子串算法目前主要包括动态规划算法(LCSstrDP)和后缀数组算法(LCSstrSA),分别用于短串和长串的最长公共子串计算.前者代码简洁,但计算速度较慢,后者速度很快但算法非常复杂.提出两种基于双向比较的最长公共子串算法,即LCSstrSeL和LCSstrSCeL.LCSstrSeL跨越已有的最长公共子串长度,与LCSstrDP相比,代码同样简洁,平均计算效率提高近一个数量级,并且不需要额外的存储空间.LCSstrSCeL是在LCSstrSeL的基础上,增加字符跨越、连续同值区间跨越等机制,平均效率较LCSstrSeL亦有一定程度的提高,内存开销与LCSstrDP相近,在中小长度的字符串LCSstr计算中,平均计算效率高于LCSstrSA,某些情况下的计算效率可达到亚线性的速度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王开云	中国工程物理研究院计算机应用研究所	21	156	7.0	12.0
2	赵强	中国工程物理研究院计算机应用研究所	25	111	7.0	9.0
3	马卫东	中国工程物理研究院电子工程研究所	35	284	11.0	15.0
4	潘泽友	中国工程物理研究院计算机应用研究所	24	162	8.0	11.0
5	孔思淇	中国工程物理研究院计算机应用研究所	7	46	4.0	6.0
6	付云生	中国工程物理研究院计算机应用研究所	1	15	1.0	1.0