Approximate string matching with pumping

Author

Robert Scott Harris

Date of Award

8-1993

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Jens Grego

Committee Members

Michael Thomason, Heather Booth

Abstract

The classic dynamic programming algorithm for computing edit distances between two strings is extended to compute the distance between a string and a class of strings represented by a regular expression. The result allows arbitrary pumping of symbols and substrings. The extended algorithm has the same complexity as the original-O(mn) where m and n are the lengths of the regular expression and the string.

Recommended Citation

Harris, Robert Scott, "Approximate string matching with pumping. " Master's Thesis, University of Tennessee, 1993.
https://trace.tennessee.edu/utk_gradthes/11898