Distanţa Levenshtein dintre două şiruri de caractere este egală cu numărul minim de operaţii necesare pentru a transforma primul şir în celălalt. Operaţiile permise sunt inserarea unui caracter, ştergerea unui caracter sau înlocuirea unui caracter cu un alt caracter.
Cerinţă
Cunoscând cele două şiruri de caractere, să se determine care este numărul minim de operaţii necesare pentru a transforma primul şir în cel de-al doilea şir.
Date de intrare
Fişierul de intrare siruri2.in conţine pe prima linie primul şir, iar pe următoarea linie se află cel de-al doilea şir.
Date de ieşire
Fişierul de ieşire siruri2.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul minim de operaţii necesare pentru a transforma primul şir în cel de-al doilea şir.
Restricţii
• Fiecare şir are cel mult 500 de caractere cu codurile ASCII cuprinse între 32 şi 127.
• Nu se face distincţie între literele mici şi cele mari.
Exemple
siruri2.in
siruri2.out
Explicaţii
abacul
barca
4
Asupra primului şir se execută următoarele operaţii:
− se şterge primul caracter a;
− se inserează un caracter r înainte de caracterul c;
− se înlocuieşte caracterul u cu a;
− se şterge caracterul l.