计算机仿真
計算機倣真
계산궤방진
COMPUTER SIMULATION
2007年
12期
97-100,116
,共5页
最长公共子串%动态规划%广义后缀树%广义后缀数组
最長公共子串%動態規劃%廣義後綴樹%廣義後綴數組
최장공공자천%동태규화%엄의후철수%엄의후철수조
高效求解2个字符串的最长公共子串(Longest Common Substring)是实现很多字符串算法的关键.文中首先给出了求解LCP问题的动态规划算法,广义后缀树算法,研究并分析了这两种算法,得出动态规划算法易于理解,但时间复杂度较高;广义后缀树算法的时间复杂度较低,但实现较为复杂并且广义后缀树占用的空间也较多.最后提出了一个新算法,该算法使用2个字符串的广义后缀数组,在保持和广义后缀树时间复杂度相等的基础上,可以简单地实现并且占用较少的空间.
高效求解2箇字符串的最長公共子串(Longest Common Substring)是實現很多字符串算法的關鍵.文中首先給齣瞭求解LCP問題的動態規劃算法,廣義後綴樹算法,研究併分析瞭這兩種算法,得齣動態規劃算法易于理解,但時間複雜度較高;廣義後綴樹算法的時間複雜度較低,但實現較為複雜併且廣義後綴樹佔用的空間也較多.最後提齣瞭一箇新算法,該算法使用2箇字符串的廣義後綴數組,在保持和廣義後綴樹時間複雜度相等的基礎上,可以簡單地實現併且佔用較少的空間.
고효구해2개자부천적최장공공자천(Longest Common Substring)시실현흔다자부천산법적관건.문중수선급출료구해LCP문제적동태규화산법,엄의후철수산법,연구병분석료저량충산법,득출동태규화산법역우리해,단시간복잡도교고;엄의후철수산법적시간복잡도교저,단실현교위복잡병차엄의후철수점용적공간야교다.최후제출료일개신산법,해산법사용2개자부천적엄의후철수조,재보지화엄의후철수시간복잡도상등적기출상,가이간단지실현병차점용교소적공간.
