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

高效求解2个字符串的最长公共子串(Longest Common Substring)是实现很多字符串算法的关键.文中首先给出了求解LCP问题的动态规划算法,广义后缀树算法,研究并分析了这两种算法,得出动态规划算法易于理解,但时间复杂度较高;广义后缀树算法的时间复杂度较低,但实现较为复杂并且广义后缀树占用的空间也较多.最后提出了一个新算法,该算法使用2个字符串的广义后缀数组,在保持和广义后缀树时间复杂度相等的基础上,可以简单地实现并且占用较少的空间.

Analysis of the Longest Common Substring Algorithm

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.