ITU

Fast and compact regular expression matching

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

View graph of relations

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
JournalTheoretical Computer Science
Volume409
Issue number3
Pages (from-to)486-496
Number of pages11
ISSN0304-3975
Publication statusPublished - 28 Dec 2008

ID: 273645