Bounds for the String Editing Problem
- 1 January 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (1) , 13-16
- https://doi.org/10.1145/321921.321923
Abstract
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.Keywords
This publication has 3 references indexed in Scilit:
- An algorithm for the distance between two finite sequencesJournal of Combinatorial Theory, Series A, 1974
- The String-to-String Correction ProblemJournal of the ACM, 1974
- Matching Sequences under Deletion/Insertion ConstraintsProceedings of the National Academy of Sciences, 1972