2005/09/22 by Bille, Philip, Farach-Colton, Martin · 1 citation
#Data Structures and Algorithms (cs.DS) #F.1.1 #F.2.0 #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.cs/0509069
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.