== include(page="template/taskheader" task_id="boring") ==
Poveste şi cerinţă...
Eşti în continuare la laboratorul de algoritmi. Laborantul şi-a mai revenit. Îşi dă jos ochelarii de soare şi spune:
Spunem că un şir de caractere $A$ este o $K-repetiţie$ dacă există un şir de caractere $B$ astfel încât $A = B + B + B + .. (de K ori în total)$, unde $+$ denotă operaţia de concatenare. Spre exemplu, "dada" este o $2-repetitie$, iar $andreiandreiandrei$ este o $3-repetitie$.
Având un şir de caractere $S$, trebuie să aflaţi câte subsecvenţe ale sale sunt $K-repetiţii$, pentru toţi $K$ de la $1$ la $|S|$.
h2. Date de intrare
Fişierul de intrare $boring.in$ ...
Fişierul de intrare $boring.in$ va contine pe prima sa linie valoarea $T$, reprezentand numarul de teste din fisier. Urmatoarele $T$ linii contin fiecare cate un sir de caractere, reprezentand sirul $S$.
h2. Date de ieşire
În fişierul de ieşire $boring.out$ ...
În fişierul de ieşire $boring.out$ se vor afla $T$ linii. Fiecare linie va contine $|S|$ valori, a $i$-a dintre acestea reprezentand numarul de subsecvente ale sirului $S$ care sunt $i-repetitii$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 1000$
* $1 ≤ |S| ≤ 300.000$
* Suma valorilor lui $|S|$ în cadrul aceluiaşi fişier de intrare este cel mult egală cu $300.000$.
* $S$ contine doar litere mici ale alfabetului englez.
* O subsecvenţă a unui şir este un subşir de elemente *consecutive* ale acestuia.
h2. Exemplu
table(example). |_. boring.in |_. boring.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
aaaaa
barbaraa
| 15 6 3 2 1
36 2 0 0 0 0 0 0
|
h3. Explicaţie
...
Notaţi că, în general, toate subsecvenţele lui $S$ sunt $1-repetiţii$.
== include(page="template/taskfooter" task_id="boring") ==
