Ən böyük alt sətir
Sıra S-in həddi bu sıranın öz prefiksi olub, S-in sonuna bərabər olan hər hansı bir prefiksdir.
Məsələn, S = abaababaabaab sırası iki (boş olmayan) həddə malikdir - ab və abaab. S = abaabaab sırası da iki həddə malikdir - ab və abaab, lakin ikinci hədd üst-üstə düşür. Təkrarlanan simvoldan ibarət uzunluğu n olan sıra, məsələn aaaaaaaa (və ya a^8), n-1 həddə malikdir. S = a^8 üçün bu həddlər: a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa.
"Öz prefiksi" anlayışı sıranın özü ilə üst-üstə düşən həddi istisna edir.
Həddin uzunluğu onun içindəki simvolların sayıdır.
Məsələni ümumiləşdirək. Tutaq ki, bütün alt sırlar S[1..i] (i=1..n) üçün ən böyük həddlərin dəyərlərini hesablamaq və onları br[1..n] massivində saxlamaq lazımdır.
Bütün alt sırlar S üçün ən böyük həddin dəyərini br massivində tapın.
Giriş verilənləri
S sırası verilir (|S| ≤ 10^6).
Çıxış verilənləri
Tək bir sətirdə formalaşdırılmış məsələnin cavabını yazın.