Masala #0554

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 20 %
2.4 (Baholar 10)
14

  

Z - massivni hosil qilish #2

Sizga ss satr berilgan bo’lib, bu satr orqali ZZ massivni hosil qilish so’raladi.

ZZ massivni hosil qilish quyidagicha amalga oshiriladi. 

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

Prefiks bu satrning 0index0-indexdan s[0...j](0j)s[0...j] (0\leq j) boshlanuvchi sub satrga aytiladi. Misol: s="abac"s = "abac" satrning prefikslari aa, abababaaba va abacabac


Kiruvchi ma'lumotlar:

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


Chiquvchi ma'lumotlar:

Chiqish faylida ZZ massiv elementlarini probel bilan ajratilgan holda bitta satrda chop eting.


Misollar
# input.txt output.txt
1
aabcaabc
0 1 0 0 4 1 0 0
2
aaaaaaa
0 6 5 4 3 2 1
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin