Skip to Main content Skip to Navigation
Conference papers

Pattern Matching on Sparse Suffix Trees

Abstract : We consider a compact text index based on evenly spaced sparse suffix trees of a text [9]. Such a tree is defined by partitioning the text into blocks of equal size and constructing the suffix tree only for those suffixes that start at block boundaries. We propose a new pattern matching algorithm on this structure. The algorithm is based on a notion of suffix links different from that of [9] and on the packing of several letters into one computer word
Document type :
Conference papers
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00681844
Contributor : Gregory Kucherov <>
Submitted on : Thursday, March 22, 2012 - 4:11:22 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Monday, November 26, 2012 - 11:56:04 AM

File

main21.pdf
Files produced by the author(s)

Identifiers

Citation

Roman Kolpakov, Gregory Kucherov, Tatiana Starikovskaya. Pattern Matching on Sparse Suffix Trees. Data Compression, Communications and Processing (CCP), University of Salerno, Jun 2011, Palinuro, Italy. pp.92-97, ⟨10.1109/CCP.2011.45⟩. ⟨hal-00681844⟩

Share

Metrics

Record views

293

Files downloads

444