Transformation – Qualification 2010

Énoncé¶

Une séquence d'ADN sera une suite finie constituée de lettres dans l'ensemble {A, T, G, C}. On vous donne en entrée deux séquences ADN de tailles N1 et N2. On souhaite calculer le nombre minimal de transformations pour passer de la première séquence à la deuxième. Les transformations possibles sont la modification, l'ajout ou la suppression d'une nucléotide. Les deux séquences sont très similaires; on garantit donc que l'on puisse passer de l'une à l'autre en moins de 100 transformations. Ecrivez un programme qui renvoie ce nombre demandé.

Contraintes¶

• 1 <= N1 <= 100000
• 1 <= N2 <= 100000
• Le nombre minimal de transformations pour passer d'une séquence à l'autre sera inférieur à 100.

Entrée¶

• Sur la première ligne, l'entier N1.
• Sur la deuxième ligne, l'entier N2.
• Sur la troisième ligne, la première séquence d'ADN, de taille N1
• Sur la quatrième ligne, la deuxième séquence d'ADN, de taille N2

Sortie¶

Un entier, indiquant le nombre minimal de transformations pour passer d'une séquence à l'autre.