求最长公共子串问题的算法分析  

Analysis of the Longest Common Substring Algorithm

作　　者：张毅超[1] 车玫[1] 马骏[1] 

机构地区：[1]中国航天科技集团公司第710研究所,北京100037

出　　处：《计算机仿真》2007年第12期97-100,116,共5页Computer Simulation

摘　　要：高效求解2个字符串的最长公共子串(Longest Common Substring)是实现很多字符串算法的关键。文中首先给出了求解LCP问题的动态规划算法,广义后缀树算法,研究并分析了这两种算法,得出动态规划算法易于理解,但时间复杂度较高;广义后缀树算法的时间复杂度较低,但实现较为复杂并且广义后缀树占用的空间也较多。最后提出了一个新算法,该算法使用2个字符串的广义后缀数组,在保持和广义后缀树时间复杂度相等的基础上,可以简单地实现并且占用较少的空间。How to solve the longest common substring of two strings efficiently is the key to many string algorithms.Firstly this paper gives two algorithms to solve LCP problem.One is the dynamic programming（DP） algorithm,and the other is generalized suffix tree（GST） algorithm.The DP algorithm is easy to implement,however with a high time complexity.The time complexity of GST algorithm is low,however it needs much more trick to implement and takes much storage space.At the end,this paper shows a generalized suffix array（GSA） algorithm which has the same time complexity as the GSA algorithm and takes less storage space than GST algorithm.

关 键 词：最长公共子串 动态规划 广义后缀树 广义后缀数组 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]