The at-most $k$-deep factor tree

Abstract : We present a new data structure to index strings that is very similar to a suffix tree. The new structure indexes the factors of a string whose length does not exceed k, and only those. We call such structure the at most k-deep factor tree, or k-factor tree for short. Time and space complexities for constructing the tree are linear in the length of the string. The construction is on-line. Compared to a suffix tree, the k-factor tree offers a substantial gain in terms of space complexity for small values of k, as well as a gain in time when used for enumerating all occurrences of a pattern in a text indexed by such a k-factor tree.
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00627813
Contributor : Julien Allali <>
Submitted on : Thursday, September 29, 2011 - 4:10:02 PM
Last modification on : Thursday, November 21, 2019 - 1:14:17 PM
Long-term archiving on: Friday, December 30, 2011 - 2:30:11 AM

File

HAL.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00627813, version 1

Collections

Citation

Julien Allali, Marie-France Sagot. The at-most $k$-deep factor tree. 2004. ⟨hal-00627813⟩

Share

Metrics

Record views

366

Files downloads

156