期刊文章详细信息
求最长公共子串问题的算法分析
Analysis of the Longest Common Substring Algorithm
文献类型：期刊文章
机构地区：[1]中国航天科技集团公司第710研究所,北京100037
年 份：2007
卷 号：24
期 号：12
起止页码：97-100
语 种：中文
收录情况：CSCD、CSCD_E2011_2012、JST、ZGKJHX、普通刊
摘 要：高效求解2个字符串的最长公共子串(Longest Common Substring)是实现很多字符串算法的关键。文中首先给出了求解LCP问题的动态规划算法,广义后缀树算法,研究并分析了这两种算法,得出动态规划算法易于理解,但时间复杂度较高;广义后缀树算法的时间复杂度较低,但实现较为复杂并且广义后缀树占用的空间也较多。最后提出了一个新算法,该算法使用2个字符串的广义后缀数组,在保持和广义后缀树时间复杂度相等的基础上,可以简单地实现并且占用较少的空间。
关 键 词：最长公共子串 动态规划 广义后缀树 广义后缀数组
分 类 号：TP301.6]
参考文献：
正在载入数据...
二级参考文献：
正在载入数据...
耦合文献：
正在载入数据...
引证文献：
正在载入数据...
二级引证文献：
正在载入数据...
同被引文献：
正在载入数据...
