Approximate string matching with pumping

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.