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

摘要：

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

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

所属期刊栏目：24

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2008-04-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：97-100,116