.png){kind=icon}
返回
Two Efficient Algorithms for Linear Time Suffix Array Construction
.png){kind=icon}
PRE
AI
DOI：10.1109/TC.2010.188.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We present, in this paper, two efficient algorithms for linear time suffix array construction. These two algorithms achieve their linear time complexities, using the techniques of divide-and-conquer, and recursion. What distinguish the proposed algorithms from other linear time suffix array construction algorithms (SACAs) are the variable-length leftmost S-type (LMS) substrings and the fixed-length d-critical substrings sampled for problem reduction, and the simple algorithms for sorting these sampled substrings: the induced sorting algorithm for the variable-length LMS substrings and the radix sorting algorithm for the fixed-length d-critical substrings. The very simple sorting mechanisms render our algorithms an elegant design framework, and, in turn, the surprisingly succinct implementations. The fully functional sample implementations of our proposed algorithms require only around 100 lines of C code for each, which is only 1/10 of the implementation of the KA [1] algorithm and comparable to that of the KS [2] algorithm. The experimental results demonstrate that these two newly proposed algorithms yield the best time and space efficiencies among all the existing linear time SACAs.
Keyword:
Suffix array
linear time
divide-and-conquer
期刊
IF:
3.8
论文数:
5.3K
被引数:
9.8K
机构
引用论文
.png){kind=icon}
分享收藏Deflection of laser-produced ions in laser-induced thermal-desorption/fourier-transform mass spectrometry for surface analysis激光诱导热脱附/傅里叶变换质谱法中激光产生离子的偏转用于表面分析
PREAI
分享收藏
查看更多内容