distância Damerau-Levenshtein
Problem
Um dos erros de digitação mais comuns é a troca de dois caracteres adjacentes, por exemplo, ao invés da palavra "programa" a palavra "programma" é digitada. A distância de Levenshtein não leva em consideração tais erros de digitação: ao calcular a distância de Levenshtein, uma permutação será contada como duas edições (por exemplo, excluir e inserir um caractere).
No cálculo da distância Damerau-Levenshtein, além das operações de substituição, inserção e exclusão de um caractere, também é permitida a operação de permuta de dois caracteres vizinhos. Ao mesmo tempo, outros caracteres não podem ser inseridos entre os caracteres reorganizados.
Determine a distância Damerau-Levenshtein para as duas strings dadas.
| Entrada |
Saída |
|
XABCDE
ACBYDF
|
4 |