Fișierul intrare/ieșire siruri2.in, siruri2.out Sursă OMI Iasi 2010
Autor Constantin Crețu Adăugată de avatar Marcela Marcela • Marcela
Timp de execuție pe test 0.1 sec Limită de memorie 3072 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Șiruri 2

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

În 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.

Exemplu

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii