Masala #0554

Sizga \(s\) satr berilgan bo’lib, bu satr orqali \(Z\) massivni hosil qilish so’raladi.

\(Z\) massivni hosil qilish quyidagicha amalga oshiriladi. 

• \(Z\) massiv elementlari soni satr elementlari soniga teng bo'ladi va \(Z\) massivning dastlabki qiymati uchun \(0\) olinadi ya'ni \(Z[0] = 0\). 
• \(Z[i] (i=1,2,...,len(s)-1)\) ni hosil qilish uchun \(s\) satrning \(i-index\)dan \(s[i...j] (i\leq j)\) boshlanuvchi eng uzun quyi satr topiladi, \(s\) satrning prefiks ga teng bo'lsin.
• Topilgan bu sub satr uzunligi \(Z[i]\) ga yoziladi (bunday satr mavjud bo'lmasa \(0\) qiymati olinadi).

Prefiks bu satrning \(0-index\)dan \(s[0...j] (0\leq j)\) boshlanuvchi sub satrga aytiladi. Misol: \(s = "abac"\) satrning prefikslari \(a\), \(ab\), \(aba\) va \(abac\)

Kirish faylida lotin alfbosining kichik harflaridan tashkil topgan \(s(1\leq |s|\leq 10^6)\) satr beriladi.

Chiqish faylida \(Z\) massiv elementlarini probel bilan ajratilgan holda bitta satrda chop eting.