Bounds for the String Editing Problem

The string editing problem is to determine the distance between two strings as measured by the minimal cost sequence of deletions, insertions, and changes of symbols needed to transform one string into the other. The longest common subsequence problem can be viewed as a special case. Wagner and Fischer proposed an algorithm that runs in time O(nm), where n, m are the lengths of the two strings. In the present paper, it is shown that if the operations on symbols of the strings are restricted to tests of equality, then O(nm) operations are necessary (and sufficient) to compute the distance. © 1976, ACM. All rights reserved.