distancia Damerau-Levenshtein
Problem
Uno de los errores tipográficos más comunes es el intercambio de dos caracteres adyacentes, por ejemplo, en lugar de la palabra "programa". se escribe la palabra "programa". La distancia de Levenshtein no tiene en cuenta esos errores tipográficos: al calcular la distancia de Levenshtein, una permutación se contará como dos ediciones (por ejemplo, eliminar e insertar un carácter).
Al calcular la distancia Damerau-Levenshtein, además de las operaciones de reemplazar, insertar y borrar un carácter, también se permite la operación de permutar dos caracteres vecinos. Al mismo tiempo, no se pueden insertar otros caracteres entre los caracteres reorganizados.
Determina la distancia Damerau-Levenshtein para las dos cadenas dadas.
| Entrada |
Salida |
|
XABCDE
ACBYDF
|
4 |