Analysis of the Longest Common Substring Algorithm
Jun Ma · Jisuanji fangzhen · 2007
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.