Fast and compact regular expression matching
- Philip Bille,
- Martin Farach-Colton
- Rutgers University
Research Output:
Journal Article or Conference Article in Journal
Journal article
Peer-reviewPublication Information
Output type
Research Output:
Journal Article or Conference Article in Journal
Journal article
Peer-reviewOriginal language
EnglishPages from-to (Number of pages)
Pages 486-496 (11 pages)Journal (Volume, Issue Number)
Theoretical Computer Science (Volume 409, Issue 3)Publication milestones
- Published - 28/12/2008
Publication status
Published - 28/12/2008
ISSN
0304-3975Publication IDs
- Scopus: 55949108676
Abstract
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.
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.
Publication metrics
PlumX
Captures
28
Citations
64