Fast and Compact Regular Expression Matching

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.

Keywords

Data Structures and Algorithms, F.2.2; F.2.0; F.1.1

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/169545

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0509069
 http://arxiv.org/abs/cs/0509069

Collections

arXiv