Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-08-05 15:26:09.
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;
  • 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).

Cerinta
Scrieti un program care sa determine numarul de lanturi de k-similitudine care incep cu c0.

Date de intrare

Fisierul de intrare lant.in contine pe prima linie valoarea k. Pe urmatoarele linii se afla textul dat.

Date de iesire

Fisierul de iesire lant.out va contine o singura linie pe care va fi scris numarul de lanturi de k-similitudine care incep cu c0.

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?