Weighted Edit Distance Computation: Strings, Trees and Dyck

Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +2

Given two strings of length $n$ over alphabet $\Sigma$, and an upper bound $k$ on their edit distance, the algorithm of Myers (Algorithmica'86) and Landau and Vishkin (JCSS'88) computes…