首页> 外文期刊>Journal of Discrete Algorithms >Constructing suffix arrays in linear time
【24h】

Constructing suffix arrays in linear time

机译:在线性时间内构造后缀数组

获取原文
获取原文并翻译 | 示例

摘要

The time complexity of suffix tree construction has been shown to be equivalent to that of sorting: O(n) for a constant-size alphabet or an integer alphabet and O(n log n) for a general alphabet. However, previous algorithms for constructing suffix arrays have the time complexity of O(n log n) even for a constant-size alphabet. In this paper we present a linear-time algorithm to construct suffix arrays for integer alphabets, which do not use suffix trees as intermediate data structures during its construction. Since the case of a constant-size alphabet can be subsumed in that of an integer alphabet, our result implies that the time complexity of directly constructing suffix arrays matches that of constructing suffix trees.
机译:后缀树构造的时间复杂度已显示出与排序相同:对于恒定大小的字母或整数字母,O(n);对于一般的字母,O(n log n)。但是,即使对于恒定大小的字母,用于构造后缀数组的先前算法也具有O(n log n)的时间复杂度。在本文中,我们提出了一种线性时间算法来构造整数字母的后缀数组,该算法在构造时不使用后缀树作为中间数据结构。由于恒定大小字母的大小写可以包含在整数字母的大小写中,因此我们的结果表明,直接构造后缀数组的时间复杂度与构造后缀树的时间复杂度匹配。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号