An Extension of the String-to-String Correction Problem

The string-to-string correction problem asks for a sequence S of "edit operations" of minimal cost such that ~(A) = B, for given strings A and B. The edit operations previously investigated allow changing one symbol of a string into another single symbol, deleting one symbol from a string, or inserting a single symbol into a string. This paper extends the set of allowable edit operations to include the operation of interchanging the positions of two adjacent characters Under certain restrictions on edit-operation costs, it is shown that the extended problem can still be solved in time proportional to the product of the lengths of the given strings.