Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds

Itai Boneh, Egor Gorbachev, Tomasz Kociumaka

The edit distance $ed(X,Y)$ of two strings $X,Y\in {\Sigma }^{\ast }$ is the minimum number of character edits (insertions, deletions, and substitutions) needed to transform $X$ into $Y$. Its we…