Zhikun Yuen, Paula Branco, et al.
DSAA 2023
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.
Zhikun Yuen, Paula Branco, et al.
DSAA 2023
Conrad Albrecht, Jannik Schneider, et al.
CVPR 2025
Arnold L. Rosenberg
Journal of the ACM
Ryan Johnson, Ippokratis Pandis
CIDR 2013