Faster suffix sorting
Faster suffix sorting
复制标题
DOI：
10.1016/j.tcs.2007.07.017
复制
发表时间：
2007-11-22
影响因子：
1.1
通讯作者：
Sadakane, Kunihiko
中科院分区：
文献类型：
--
作者：
Larsson, N. Jesper;Sadakane, Kunihiko
本文提出了一种快速高效的后缀字典排序算法，该算法在数据压缩和字符串匹配中有着重要的应用，在保持其对退化输入的稳健性的同时，消除了以前专门方法的大量开销。对于输入长度为n的两个整数数组，该算法的最坏时间复杂度为O(Nlogn)，实验结果表明，该算法与其他方法相比具有稳定的性能。(C)2007 Elsevier B.V.保留所有权利。
We propose a fast and memory-efficient algorithm for lexicographically sorting the suffixes of a string, a problem that has important applications in data compression as well as string matching.Our algorithm eliminates much of the overhead of previous specialized approaches while maintaining their robustness for degenerate inputs. For input size n, our algorithm operates in only two integer arrays of size n, and has worst-case time complexity O(n log n).We demonstrate experimentally that our algorithm has stable performance compared with other approaches. (c) 2007 Elsevier B.V. All rights reserved.