Problem
Data una stringa di testo. Puoi eseguire le seguenti operazioni con esso:
1. Sostituisci un carattere di una stringa con un altro carattere.
2. Elimina un carattere arbitrario.
3. Inserisci un carattere arbitrario in una posizione arbitraria nella stringa.
Ad esempio, utilizzando la prima operazione della stringa "JUICE" puoi ottenere la stringa "SUK", usando la seconda operazione - la stringa "OK", usando la terza operazione - la stringa "STOCK.
Il numero minimo di tali operazioni che possono essere utilizzate per ottenerne un'altra da una stringa รจ chiamato costo di modifica o distanza di Levenshtein.
Trova la distanza di Levenshtein per le due stringhe date.
Input
Il programma riceve in input due stringhe, la lunghezza di ognuna delle quali non supera i 1000 caratteri, le stringhe sono composte solo da lettere latine maiuscole.
Uscita
Obbligatorio per produrre un singolo numero – Distanza di Levenshtein per determinate stringhe.
| Input |
Uscita |
|
ABCDEFGH
ACDEXGIH
|
3 |