mesaj2

Mesaj 2

== include(page="template/taskheader" task_id="mesaj2") ==

Poveste si cerinta...

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).
 
h2. Cerinta
 
Aflati pentru fiecare lexicograf numarul de cuvinte din mesajul descifrat de el.

h2. 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$.

h2. 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$.

h2. 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.

h2. Exemplu
table(example). |_. mesaj2.in |_. mesaj2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| omuliosu
  6
  omul
  iscusit
  lis
  om
  ou
  li
| 1
  1
  1
  2
  2
  3

|

h3. Explicatie

h3. 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$

== include(page="template/taskfooter" task_id="mesaj2") ==

1852