Constant-time word-size string matching

Dany Breslauer, Leszek Ga̧sieniec, Roberto Grossi

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

5 Scopus citations


We present a novel string-matching algorithm that requires constant time for text scanning in an unusual model where (a) the input pattern and text are each packed into a single word, (b) the output is a one word bit-mask identifying the pattern occurrences in the text, and (c) there are constant-time arithmetic, bitwise, and shift instructions that operate on words whose size is proportional to the arbitrarily long input length. Our bit-parallelism techniques build upon and also greatly simplify existing parallel random access machine algorithms by using two "simple structure" rather than "small size" deterministic samples, i.e., one deterministic sample is very small (size two), while the other is a potentially very long prefix of the pattern. Pattern preprocessing takes time proportional to the word size. Our results also establish, by recent reductions, new bounds for the packed string matching problem.

Original languageEnglish (US)
Title of host publicationCombinatorial Pattern Matching - 23rd Annual Symposium, CPM 2012, Proceedings
Number of pages14
StatePublished - 2012
Externally publishedYes
Event23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012 - Helsinki, Finland
Duration: Jul 3 2012Jul 5 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7354 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Constant-time word-size string matching'. Together they form a unique fingerprint.

Cite this