siruri

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 siruri.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 siruri.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 şi precizări

• 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.

Exemplul 1

siruri.in

abacul
barca

siruri.out

4

Explicație

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.

Exemplul 2

siruri.in

Ana are mere
Mana tremura

siruri.out

5

Explicație

Asupra primului şir se execută următoarele operaţii:

• se inserează pe prima poziţie caracterul M;
• se înlocuieşte al treilea caracter a cu t
• se şterge al doilea caracter spaţiu
• se înlocuieşte al doilea caracter e cu u
• se înlocuieşte ultimul caracter e cu a