Pattern Matching on Sparse Suffix Trees

Roman Kolpakov (1) , Gregory Kucherov (2) , Tatiana Starikovskaya (1)

1 Faculty of Mechanics and Mathematics
2 LIGM - Laboratoire d'Informatique Gaspard-Monge

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

Domaines: Algorithme et structure de données [cs.DS]

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⟩