String distance problems typically ask for a minimum number of permitted operations to transform one string into another. Such problems find application in a wide variety of areas, including error-correcting codes, parsing ...