Distanza Damerau-Levenshtein
Problem
Uno degli errori di battitura più comuni è lo scambio di due caratteri adiacenti, ad esempio, al posto della parola "programma" viene digitata la parola "programma". La distanza di Levenshtein non tiene conto di tali errori di battitura: quando si calcola la distanza di Levenshtein, una permutazione verrà conteggiata come due modifiche (ad esempio, l'eliminazione e l'inserimento di un carattere).
Nel calcolo della distanza Damerau-Levenshtein, oltre alle operazioni di sostituzione, inserimento e cancellazione di un carattere, è consentita anche l'operazione di permutazione di due caratteri vicini. Allo stesso tempo, non è possibile inserire altri caratteri tra i caratteri riorganizzati.
Determina la distanza Damerau-Levenshtein per le due stringhe date.
| Input |
Uscita |
|
XABCDE
ACBYDF
|
4 |