Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-08-05 15:22:05.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:lant.in, lant.outSursăOJI 2005, clasele 11-12
AutorEmanuela CerchezAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.1 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Lant

Ion este un lingvist pasionat. Recent el a descoperit un text scris intr-o limba necunoscuta. Textul este scris pe mai multe linii si este format din cuvinte scrise cu litere mici din alfabetul latin, separate prin spatii sau/si semne de punctuatie (,:;.!?-).
Ion a fost frapat ca exista multe similitudini intre cuvintele din text. Fiind foarte riguros, Ion defineste similitudinea a doua cuvinte dupa cum urmeaza.
Fie c1 si c2 doua cuvinte. Cuvantul c1 poate fi obtinut din cuvantul c2 printr-o succesiune de operatii elementare. Operatiile elementare ce pot fi folosite sunt:

Operatia
Efect
Exemplu
move(c1,c2)
Muta primul caracter din c1 la sfarsitul cuvantului c2
Daca c1="alba" si c2="neagra", dupa efectuarea operatiei move(c1, c2), c1 va fi "lba", iar c2 va fi "neagraa".
insert(c1,x)
Insereaza caracterul x la inceputul lui c1
Daca c1="alba" si x='b', dupa executarea operatiei insert(c1,x), c1 va fi "balba".
delete(c1)
Sterge primul caracter din c1
Daca c1="alba", dupa executarea operatiei delete(c1), c1 va fi "lba".

Definim similitudinea dintre c1 si c2 ca fiind numarul minim de operatii insert si delete ce trebuie sa fie executate pentru a transforma cuvantul c1 in cuvantul c2 (operatiile move nu se numara).
Fie c0 primul cuvant din text. Incepand cu c0 putem construi lanturi de k-similitudine.
Un lant de k-similitudine este o succesiune de cuvinte distincte din text cu urmatoarele proprietati:
* daca cuvantul x apare in lant inaintea cuvantului y, atunci prima aparitie a lui x in text preceda prima aparitie a lui y in text;
* dacă x si y sunt cuvinte consecutive in lant (in ordinea x y) , atunci similitudinea dintre x si y este ≤ k;
* lantul este maximal (adica nu putem adauga inca un cuvant la sfarsitul acestui lant, astfel incat sa fie respectate proprietatile precedente).

Date de intrare

...

Date de iesire

...

Restrictii

  • ... ≤ ... ≤ ...

Exemplu

lant.inlant.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicatie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?