Advertisement
Published in:
2007 | OriginalPaper | Chapter
A Simple Construction of Two-Dimensional Suffix Trees in Linear Time
(Extended Abstract)
Authors : Dong Kyue Kim, Joong Chae Na, Jeong Seop Sim, Kunsoo Park
Published in: Combinatorial Pattern Matching
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The two-dimensional suffix tree of a matrix
A
is a compacted trie that represents all square submatrices of
A
. There exists a linear-time construction of two-dimensional suffix trees using the
odd-even
scheme. This algorithm has the drawback that the merging step is quite complicated. In this paper, we propose a new and simple algorithm to construct two-dimensional suffix trees in linear time by applying the
skew
scheme to square matrices. To do this, we present a simple algorithm to merge two Isuffix trees in linear time.