Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | lant.in, lant.out | Sursă | OJI 2005, clasele 11-12 |
| Autor | Emanuela Cerchez | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 4736 kbytes |
| Scorul tău | N/A | Dificultate | N/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;
- daca 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.in | lant.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
