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 operatieimove(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 mai mica sau egala cu 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

  • Lungimea unei linii din text nu depaseste 1000 de caractere.
  • Lungimea unui cuvant nu depaseste 30 de caractere.
  • Numarul total de cuvinte distincte ≤ 150.
  • Pentru datele de test, numarul de lanturi de k-similitudine care incep cu c0 va fi ≤2000000000 (doua miliarde).

Exemplu

lant.inlant.out
5
ana are mere, banane,
pere si castane.
6

Explicatie

Lanturile de 5-similitudine care se pot forma sunt:
ana are mere pere
ana are pere
ana are banane castane
ana are si
ana banane castane
ana si

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content