王开云, 孔思淇, 付云生, 潘泽友, 马卫东, 赵 强. 两种基于双向比较的最长公共子串算法[J]. 计算机研究与发展, 2013, 50(11): 2444-2454.
 引用本文: 王开云, 孔思淇, 付云生, 潘泽友, 马卫东, 赵 强. 两种基于双向比较的最长公共子串算法[J]. 计算机研究与发展, 2013, 50(11): 2444-2454.
Wang Kaiyun, Kong Siqi, Fu Yunsheng, Pan Zeyou, Ma Weidong, Zhao Qiang. Two Longest Common Substring Algorithms Based on Bi-Directional Comparison[J]. Journal of Computer Research and Development, 2013, 50(11): 2444-2454.
 Citation: Wang Kaiyun, Kong Siqi, Fu Yunsheng, Pan Zeyou, Ma Weidong, Zhao Qiang. Two Longest Common Substring Algorithms Based on Bi-Directional Comparison[J]. Journal of Computer Research and Development, 2013, 50(11): 2444-2454.

## Two Longest Common Substring Algorithms Based on Bi-Directional Comparison

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

Abstract: Finding the longest common substring (LCSstr) for two given strings is an important problem in string analysis. It can be used in many applications such as approximate string matching, biological sequences analysis, plagiarism detection and computer virus signature detection. There are two algorithms to solve the longest common substring problem: Dynamic programming (LCSstrDP) and the suffix array (LCSstrSA). LCSstrDP solves the LCSstr problem by calculating the longest common suffix of the prefix (comparing from right to left). Its code is simple, but of low efficientcy LCSstrSA calculates the longest common prefix of the suffix (comparing from left to right). LCSstrSA’s time complexity is linear, though it is more complex. In this paper, we propose two LCSstr algorithms based on bi-directional comparison, named LCSstrSeL and LCSstrSCeL. LCSstrSeL skips the existing length of LCSstr with simple code and significantly improved efficiency, compared with LCSstrDP. On the basis of LCSstrSeL, LCSstrSCeL adds several mechanisms, such as character and continuous same value segment spanning. The test results show that not only the memory overhead of the algorithm is lower than that of LCSstrSA, but also the average efficiency is higher for small and medium strings. In some case the computation efficiency can be sublinear.

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈