Siklik şəkilçilər (Asan)
Riyaziyyat S = s_1s_2s_3...s_{n - 1}s_n əlifbası üzərində Σ nəzərdən keçirək. m dərəcəli dairəvi genişlənmə adlanan S sıranın s_1s_2s_3...s_{n - 1}s_ns_1s_2... m simvoldan ibarət olan hissəsidir; yəni, biz S sıranı özünə əlavə edirik, lazım olan uzunluğu əldə edənə qədər, və m uzunluğunda prefiks götürürük.
Dairəvi sıra Š adlanan S sıranın sonsuz dairəvi genişlənməsidir.
Dairəvi sıra Š sufixlərini nəzərdən keçirək. Aydındır ki, ən çoxu |S| fərqli sufix mövcuddur: (n+1)-ci sufix birinci ilə üst-üstə düşür, (n+2)-ci ikinci ilə üst-üstə düşür və s. Bundan əlavə, fərqli sufixlərin sayı daha az ola bilər. Məsələn, əgər S = abab olarsa, dairəvi sıra Š ilk dörd sufixi belədir:
Š_1 = ababababab...Š_2 = bababababa...Š_3 = ababababab...Š_4 = bababababa...
Burada cəmi iki fərqli sufix mövcuddur, halbuki |S| = 4.
İlk |S| sufixlərini leksikoqrafik olaraq sıralayaq. Əgər iki sufix üst-üstə düşərsə, daha kiçik indeksli sufixi birinci qoyarıq. İndi bizi maraqlandıran sual budur: bu siyahıda sıranın özü Š hansı yerdədir?
Məsələn, S = cabcab sıranı nəzərdən keçirək:
(1) Š_2 = abcabcabca...(2) Š_5 = abcabcabca...(3) Š_3 = bcabcabcab...(4) Š_6 = bcabcabcab...(5) Š_1 = cabcabcabc...(6) Š_4 = cabcabcabc...
Burada dairəvi sıra Š = Š_1 beşinci yerdədir.
Sizə sıra S verilir. Sizin vəzifəniz təsvir olunan qaydada dairəvi sıra Š mövqeyini tapmaqdır.
Giriş verilənləri
Giriş faylında tək bir sıra S (1 ≤ |S| ≤ 30) yazılmışdır, böyük latın hərflərindən ibarətdir.
Çıxış verilənləri
Çıxış faylında təsvir olunan qaydada ilk |S| sufixlər arasında Š sıranın nömrəsini yazın.