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 条
  • [1] Amir A.(1992)Two-dimensional dictionary matching Inf. Process. Lett. 21 233-239
  • [2] Farach M.(1996)Parameterized pattern matching: Algorithms and applications J. Comput. Syst. Sci. 52 28-42
  • [3] Baker B.(2003)Faster suffix tree construction with missing suffix links SIAM J. Comput. 33 26-42
  • [4] Cole R.(1979)On the complexity of computations under varying set of primitives J. Comput. Syst. Sci. 18 86-91
  • [5] Hariharan R.(2000)On the sorting-complexity of suffix tree construction J. ACM 47 987-1011
  • [6] Dobkin D.(1995)A generalization of the suffix tree to square matrices, with application SIAM J. Comput. 24 520-562
  • [7] Lipton R.(1996)On the construction of classes of suffix trees for square matrices: algorithms and applications Inf. Comput. 130 151-182
  • [8] Farach-Colton M.(1999)On-line construction of two-dimensional suffix trees J. Complex. 15 72-127
  • [9] Ferragina P.(1984)Fast algorithms for finding nearest common ancestors SIAM J. Comput. 13 338-355
  • [10] Muthukrishnan S.(2006)Linear work suffix array construction J. ACM 53 918-936
12345