TY - JOUR
T1 - Fast and compact regular expression matching
AU - Bille, Philip
AU - Farach-Colton, Martin
N1 - Funding Information:
Thanks to the anonymous reviewers for many detailed and insightful comments. The first author’s research was supported by the Danish Agency for Science, Technology, and Innovation.
PY - 2008/12/28
Y1 - 2008/12/28
N2 - 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.
AB - 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.
KW - Approximate regular expression matching: String edit distance
KW - Four russian technique
KW - Regular expression matching
KW - Subsequence indexing
UR - http://www.scopus.com/inward/record.url?scp=55949108676&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=55949108676&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2008.08.042
DO - 10.1016/j.tcs.2008.08.042
M3 - Article
AN - SCOPUS:55949108676
SN - 0304-3975
VL - 409
SP - 486
EP - 496
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 3
ER -