Se dă un şir de caractere de lungime L. Acest şir conţine un mesaj ascuns şi a fost obţinut prin concatenarea cuvintelor care formau mesajul şi apoi inserarea unor caractere întâmplătoare la poziţii întâmplătoare în şir. N lexicografi s-au decis să descifreze mesajul. În acest scop, lexicografii vin pe rând (în ordine, de la 1 la N) şi fiecare lexicograf adaugă un cuvânt la un dicţionar. Iniţial dicţionarul este vid.
După ce a adăugat cuvântul, fiecare lexicograf încearcă să descopere mesajul ascuns în şir.
În acest scop, lexicograful partiţionează şirul într-un număr maxim de subsecvenţe, astfel încât fiecare subsecvenţă să conţină ca subşir unul dintre cuvintele existente în dicţionar la momentul respectiv. Deci numărul maxim de subsecvenţe în care a fost partiţionat şirul reprezintă de fapt numărul de cuvinte din mesaj identificate de lexicograf (cuvintele din mesaj nu sunt în mod necesar distincte).
Cerinţă
Aflaţi pentru fiecare lexicograf numărul de cuvinte din mesajul descifrat de el.
Date de intrare
Pe prima linie a fişierului de intrare mesaj2.in se află şirul de caractere dat. Pe a doua linie se află numărul întreg N care reprezintă numărul de lexicografi. Pe fiecare dintre următoarele N linii se află câte un şir de caractere. Mai exact, pe cea de a i-a linie dintre cele N se află cuvântul adăugat la dicţionar de lexicograful i.
Date de ieşire
Fişierul de ieşire mesaj2.out va conţine N linii. Pe linia i va fi scris numărul de cuvinte ale mesajului descifrat de lexicograful i.
Restricţii
• 1 ≤ L ≤ 1000
• 1 ≤ N ≤ 5000
• Atât cuvintele cât şi şirul dat sunt formate din caractere cu coduri ASCII de la 33 la 127 (deci nu conţin spaţii)
• Lungimile cuvintelor nu vor depăşi L
• Se face distincţie între majuscule şi minuscule (a este diferit de A)
• Suma lungimilor cuvintelor este mai mică sau egală cu 10000
• O subsecvenţă a unui şir este formată din caractere consecutive din şirul respectiv.
• Un subşir al unui şir este format din caractere (nu neapărat consecutive) ale şirului respectiv, în ordinea în care acestea apar în şir.
Exemple
mesaj2.in
mesaj2.out
Explicaţii
omuliosu
6
omul
iscusit
lis
om
ou
li
1
1
1
2
2
3
Mesaje posibile:
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