Fast and Compact Regular Expression Matching

Simple item page
dc.creatorBille, Philip
dc.creatorFarach-Colton, Martin
dc.date2005-09-22
dc.date2008-09-22
dc.date.accessioned2026-07-07T10:04:06Z
dc.date.available2026-07-07T10:04:06Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/cs/0509069
dc.identifierhttp://arxiv.org/abs/cs/0509069
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/169545
dc.subjectData Structures and Algorithms
dc.subjectF.2.2; F.2.0; F.1.1
dc.titleFast and Compact Regular Expression Matching
dc.typetext

Files

Collections

arXiv