Module: Plus grande sous-séquence commune

L'une des erreurs de frappe les plus courantes est l'échange de deux caractères adjacents, par exemple, au lieu du mot "programme" le mot "programma" est tapé. La distance de Levenshtein ne tient pas compte de ces fautes de frappe : lors du calcul de la distance de Levenshtein, une permutation sera comptée comme deux modifications (par exemple, la suppression et l'insertion d'un caractère).

 

Lors du calcul de la distance Damerau-Levenshtein, en plus des opérations de remplacement, d'insertion et de suppression d'un caractère, l'opération de permutation de deux caractères voisins est également autorisée. En même temps, d'autres caractères ne peuvent pas être insérés entre les caractères réarrangés.

 

Déterminez la distance Damerau-Levenshtein pour les deux chaînes données.
 

XABCDE

ACBYDF

Entrée	Sortie
4