Multidimensional matching and fast search in suffix trees

Richard Cole, Moshe Lewenstein

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We show how to construct a suffix tree of a text string t in linear time, after sorting the characters in the text, so that a search for pattern p take time O(p + log t), independent of the alphabet size, thereby matching the asymptotic performance of suffix arrays. Using these suffix trees or suffix arrays we then give linear time algorithms for pattern matching in any fixed dimension.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
EditorsJ Schewel
Pages851-852
Number of pages2
StatePublished - 2003
EventConfiguralble Computing: Technology and Applications - Boston, MA, United States
Duration: Nov 2 1998Nov 3 1998

Other

OtherConfiguralble Computing: Technology and Applications
CountryUnited States
CityBoston, MA
Period11/2/9811/3/98

ASJC Scopus subject areas

  • Chemical Health and Safety
  • Software
  • Safety, Risk, Reliability and Quality
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Multidimensional matching and fast search in suffix trees'. Together they form a unique fingerprint.

  • Cite this

    Cole, R., & Lewenstein, M. (2003). Multidimensional matching and fast search in suffix trees. In J. Schewel (Ed.), Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 851-852)