6533b860fe1ef96bd12c2ea9
RESEARCH PRODUCT
On the construction of classes of suffix trees for square matrices: Algorithms and applications
Roberto GrossiRaffaele Giancarlosubject
CombinatoricsCompressed suffix arraylawSuffix treeString (computer science)Generalized suffix treeSuffix arraySuffixAlgorithmFM-indexlaw.inventionMathematicsLongest common substring problemdescription
Given an n × n TEXT matrix with entries defined over an ordered alphabet σ, we introduce 4n−1 classes of index data structures for TEXT. Those indices are informally the two-dimensional analog of the suffix tree of a string [15], allowing on-line searches and statistics to be performed on TEXT. We provide one simple algorithm that efficiently builds any chosen index in those classes in O(n2 log n) worst case time using O(n2) space. The algorithm can be modified to require optimal O(n2) expected time for bounded σ.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1995-01-01 |