| Fişierul intrare/ieşire: | mesaj2.in, mesaj2.out | Sursă | Lot 2004 |
| Autor | Radu Berinde | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Mesaj2
Se da un sir de caractere de lungime L. Acest sir contine un mesaj ascuns si a fost obtinut prin concatenarea cuvintelor care formau mesajul si apoi inserarea unor caractere intamplatoare la pozitii intamplatoare in sir. N lexicografi s-au decis sa descifreze mesajul. In acest scop, lexicografii vin pe rand (in ordine, de la 1 la N) si fiecare lexicograf adauga un cuvant la un dictionar. Initial dictionarul este vid. Dupa ce a adaugat cuvantul, fiecare lexicograf incearca sa descopere mesajul ascuns in sir. In acest scop, lexicograful partitioneaza sirul intr-un numar maxim de subsecvente, astfel incat fiecare subsecventa sa contina ca subsir unul dintre cuvintele existente in dictionar la momentul respectiv. Deci numarul maxim de subsecvente in care a fost partitionat sirul reprezinta de fapt numarul de cuvinte din mesaj identificate de lexicograf (cuvintele din mesaj nu sunt in mod necesar distincte).
Cerinta
Aflati pentru fiecare lexicograf numarul de cuvinte din mesajul descifrat de el.
Date de intrare
Pe prima linie a fisierului de intrare mesaj2.in se afla sirul de caractere dat. Pe a doua linie se afla numarul intreg N care reprezinta numarul de lexicografi. Pe fiecare dintre urmatoarele N linii se afla cate un sir de caractere. Mai exact, pe cea de a i-a linie dintre cele N se afla cuvantul adaugat la dictionar de lexicograful i.
Date de iesire
Fisierul de iesire mesaj2.out va contine N linii. Pe linia i va fi scris numarul de cuvinte ale mesajului descifrat de lexicograful i.
Restrictii
- 1 ≤ L ≤ 1000
- 1 ≤ N ≤ 5000
- Atat cuvintele cat si sirul dat sunt formate din caractere cu coduri ASCII de la 33 la 127 (deci nu contin spatii)
- Lungimile cuvintelor nu vor depasi L
- Se face distinctie intre majuscule si minuscule ( a este diferit de A)
- Suma lungimilor cuvintelor este mai mica sau egala cu 10000
- O subsecventa a unui sir este formata din caractere consecutive din sirul respectiv
- Un subsir al unui sir este format din caractere (nu neaparat consecutive) ale sirului respectiv, in ordinea in care acestea apar in sir.
Exemplu
| mesaj2.in | mesaj2.out |
|---|---|
| omuliosu 6 omul iscusit lis om ou li | 1 1 1 2 2 3 |
Explicatie
Mesajele posibile (in ordinea in care apar in fisierul de intrare):
omul
omul
omul sau lis
om lis
om lis sau ou lis sau om ou sau ou ou
om li ou sau ou li ou
