Linear-Time Construction of Two-Dimensional Suffix Trees

被引：0
作者：
Dong Kyue Kim
Joong Chae Na
Jeong Seop Sim
Kunsoo Park
机构：
[1] Hanyang University,Department of Electronics and Communications Engineering
[2] Sejong University,Department of Computer Science and Engineering
[3] Inha University,School of Computer and Information Engineering
[4] Seoul National University,School of Computer Science and Engineering
来源：
Algorithmica | 2011年 / 59卷
关键词：
Suffix tree; Two-dimensional suffix tree; Divide-and-conquer approach;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The two-dimensional suffix tree of a matrix A is a compacted tree that represents all square submatrices of A. We present the first complete version of a deterministic linear-time algorithm to construct the two-dimensional suffix tree by applying a divide-and-conquer approach.
引用
收藏
页码：269 / 297
页数：28
相关论文
共 41 条
  • [11] Giancarlo R.(2003)Generalizations of suffix arrays to multi-dimensional matrices Theor. Comput. Sci. 302 401-416
  • [12] Giancarlo R.(2005)Constructing suffix arrays in linear time J. Discrete Algorithms 3 126-142
  • [13] Grossi R.(2005)Space efficient linear time construction of suffix arrays J. Discrete Algorithms 3 143-156
  • [14] Giancarlo R.(1976)A space-economical suffix tree construction algorithm J. ACM 23 262-272
  • [15] Guaiana D.(2007)On-line construction of two-dimensional suffix trees in Algorithmica 48 173-186
  • [16] Harel D.(1981)( J. ACM 28 16-24
  • [17] Tarjan R.(1988)log  SIAM J. Comput. 17 1253-1262
  • [18] Kärkkäinen J.(1983)) time J. Comput. Syst. Sci. 26 362-391
  • [19] Sanders P.(1995)Linear algorithm for data compression via string matching Algorithmica 14 249-260
  • [20] Burkhardt S.(undefined)On finding lowest common ancestors: Simplification and parallelization undefined undefined undefined-undefined
12345