Fast and Compact Regular Expression Matching
<|reference_start|>Fast and Compact Regular Expression Matching: 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.<|reference_end|>
@article{bille2005fast,
    title={Fast and Compact Regular Expression Matching},
    author={Philip Bille and Martin Farach-Colton},
    journal={arXiv preprint arXiv:cs/0509069},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0509069},
    primaryClass={cs.DS}
}