Information

Deadline Geen deadline
Submission limit No limitation

Sign in

[5.18] Edit Distance [15min]

On va calculer la distance d'édition entre deux chaines de caractères. Cette distance représente le coût de transformer une chaine de caractères en une autre.

Les opérations définies sont :

  • insérer un nouveau caractère
  • changer un caractère en un autre
  • copier un caractère
  • supprimer un caractère
  • supprimer le reste de la chaine

Toutes les opérations ont un coût de 1 à l'exception de copier un caractère qui a un coût de 0.

Pour vous aider, on vous donne déjà le type Edit, les signatures des fonctions à implémenter et le pseudo-code :

cost = la longueur de la liste d'édits sans les Copy

best = la liste d'édits dont le coût est le plus bas

transform xs ys =
  si xs == [] et ys == [] alors
    []
  sinon si xs != [] et ys == [] alors
    [Kill]
  sinon si xs == [] alors
    insertion des valeurs de ys
  sinon si xs[0] == ys[0] alors
    [Copy] + transform récursif sur xs[1:] et ys[1:]
  sinon
    [opération la moins coûteuse entre Delete, Insert ys[0] et Change ys[0]] + transform récursif sur xs[1:] et ys[1:]

Le code