Indexed Dynamic Programming to boost Edit Distance and LCSS Computation

Jérémy Barbay, Andrés Olivares

There are efficient dynamic programming solutions to the computation of the Edit Distance from $S\in [\mathrm{1..}\sigma {]}^n$ to $T\in [\mathrm{1..}\sigma {]}^m$, for many natural subsets of edit operations, typica…