| 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 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.in | lant.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
