• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

Pattern Matching on Sparse Suffix Trees

P. 92-97.
Kolpakov R. M., Kucherov G., Starikovskaya T.

We consider a compact text index based on evenly spaced sparse suffix trees of a text \cite{KU-96}. 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~\cite{KU-96} and on the packing of several letters into one computer word.

In book

Edited by: B. Carpentieri, F. Palmieri. NY: IEEE Computer Society, 2013.