Problem
Étant donné une chaîne de texte. Vous pouvez effectuer les opérations suivantes avec :
1. Remplacez un caractère d'une chaîne par un autre caractère.
2. Supprimer un caractère arbitraire.
3. Insérer un caractère arbitraire à une position arbitraire dans la chaîne.
Par exemple, en utilisant la première opération de la chaîne "JUICE" vous pouvez obtenir la chaîne "SUK", en utilisant la deuxième opération - la chaîne "OK", en utilisant la troisième opération - la chaîne "STOCK.
Le nombre minimum d'opérations de ce type pouvant être utilisées pour en obtenir une autre à partir d'une chaîne est appelé le coût d'édition ou la distance de Levenshtein.
Trouvez la distance de Levenshtein pour les deux chaînes données.
Entrée
Le programme reçoit deux chaînes en entrée, dont la longueur de chacune ne dépasse pas 1000 caractères, les chaînes se composent uniquement de lettres latines majuscules.
Sortie
Requis pour générer un seul numéro – Distance Levenshtein pour des cordes données.
| Entrée |
Sortie |
ABCDEFGH
ACDEXGIH
3 |