• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

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.

В книге

Под науч. редакцией: B. Carpentieri, F. Palmieri. NY: IEEE Computer Society, 2013.