Fast and compact regular expression matching

Philip Bille, Martin Farach-Colton

    Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review


    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.
    TidsskriftTheoretical Computer Science
    Udgave nummer3
    Sider (fra-til)486-496
    Antal sider11
    StatusUdgivet - 28 dec. 2008