Rendre deux chaînes identiques – Qualification 2002

Level 2

ENONCE

On vous donne deux suites de caractères alphanumériques. Ecrire 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.

CONTRAINTES

  • 0 \<= N \<= 1000, où N est le nombre de caractères de la première suite.

  • 0 \<= M \<= 1000, où M est le nombre de caractères de la deuxième suite.

ENTREE

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.

Runtime constraints

Maximum memory usage
5000 kilobytes
Maximum execution time
500 milliseconds

Input/output samples

Submit your solution

You have to register or log in to be able to submit your solution.