Distance d'édition
La distance d’édition entre deux chaînes de caractères est le nombre minimal d’opérations nécessaires pour transformer l’une en l’autre. Les opérations autorisées sont :
- Ajouter un caractère à la chaîne.
- Supprimer un caractère de la chaîne.
- Remplacer un caractère dans la chaîne.
Par exemple, la distance d’édition entre et est 2, car vous pouvez d’abord remplacer par , puis ajouter .
Étant données deux chaînes de caractères, votre tâche consiste à calculer la distance d’édition entre ces deux chaînes.
Entrée
La première ligne de l’entrée contient la première chaîne de caractères, tandis que la deuxième ligne contient la deuxième chaîne de caractères. Il est garanti que le nombre de caractères dans les chaînes ne dépasse pas 1000.
Sortie
Le programme doit afficher un seul entier : la distance d’édition entre les deux chaînes données.
Exemples
Entrée | Sortie |
love
movie | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB