Fast and compact regular expression matching

Philip Bille, Martin Farach-Colton

Research output: Contribution to journalArticlepeer-review

54 Scopus citations


We study 4 problems in string matching, namely, regular expression matching, approximate regular expression matching, string edit distance, and subsequence indexing, on a standard word RAM model of computation that allows logarithmic-sized words to be manipulated in constant time. We show how to improve the space and/or remove a dependency on the alphabet size for each problem using either an improved tabulation technique of an existing algorithm or by combining known algorithms in a new way.

Original languageEnglish (US)
Pages (from-to)486-496
Number of pages11
JournalTheoretical Computer Science
Issue number3
StatePublished - Dec 28 2008

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


  • Approximate regular expression matching: String edit distance
  • Four russian technique
  • Regular expression matching
  • Subsequence indexing


Dive into the research topics of 'Fast and compact regular expression matching'. Together they form a unique fingerprint.

Cite this