Fişierul intrare/ieşire:mesaj2.in, mesaj2.outSursăLot 2004
AutorRadu BerindeAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.025 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inmesaj2.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content