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:]
INGInious