Fişierul intrare/ieşire:boring.in, boring.outSursăACM-ICPC Faza Nationala 2018
AutorAdrian Budau, Mihai CalanceaAdăugată de
Timp execuţie pe test6 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Boring

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

Date de intrare

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.

Date de ieşire

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

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.

Exemplu

boring.inboring.out
2
aaaaa
barbaraa
15 6 3 2 1
36 2 0 0 0 0 0 0

Explicaţie

Notaţi că, în general, toate subsecvenţele lui S sunt 1-repetiţii.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?