An Algorithmic Bridge Between Hamming and Levenshtein Distances

Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer +1

The edit distance between strings classically assigns unit cost to every character insertion, deletion, and substitution, whereas the Hamming distance only allows substitutions. In…