Name
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. |
Year | DOI | Venue |
|---|---|---|
1976 | 10.1145/321921.321923 | J. ACM |
Keywords | DocType | Volume |
special case,longest common subsequence,minimal cost sequence,present paper,time O,bounds for computing edit distance,String Editing Problem,string editing problem,longest common subsequence problem,. strlng editing | Journal | 23 |
Issue | ISSN | Citations |
1 | 0004-5411 | 65 |
PageRank | References | Authors |
47.48 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| C. K. Wong | 1 | 1459 | 513.44 |
| Ashok K. Chandra | 2 | 3116 | 1215.02 |