A dynamic edit distance table. (English) Zbl 0964.68567
Giancarlo, Raffaele (ed.) et al., Combinatorial pattern matching. 11th annual symposium, CPM 2000. Montréal, Canada, June 21-23, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1848, 60-68 (2000).
Summary: We consider the incremental/decremental version of the edit distance problem: given a solution to the edit distance between two strings \(A\) and \(B\), find a solution to the edit distance between \(A\) and \(B'\) where \(B'= aB\) (incremental) or \(bB'= B\) (decremental). As a solution for the edit distance between \(A\) and \(B\), we define the difference representation of the \(D\)-table, which leads to a simple and intuitive algorithm for the incremental/decremental edit distance problem.
For the entire collection see [Zbl 0944.00072].
For the entire collection see [Zbl 0944.00072].
