Rendre deux chaînes identiques – Qualification 2002

Énoncé¶

On vous donne deux suites de caractères alphanumériques. Écrire un programme qui renvoie le nombre minimum d'opérations à effectuer sur la deuxième suite, pour la rendre identique à la première. Les opérations autorisées sont l'insertion d'un caractère, et la suppression d'un caractère.

Entrée¶

On vous fournit 4 lignes sur l'entrée standard :

• Le nombre $N$ de caractères de la première suite.

• Les caractères de la première suite, sans séparations.

• Le nombre $M$ de caractères de la deuxième suite.

• Les caractères de la deuxième suite, sans séparations.

Sortie¶

Vous devez écrire une ligne sur la sortie standard :

• Le nombre d'opérations à effectuer.

Contraintes¶

• $0 <= N <= 1000$
• $0 <= M <= 1000$