უცნაური საჭმელი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: IBSU, 2015, ზამთრის ოლიმპიადა, VII-VIII


ბაქარი პატარაობიდანვე ცნობილი იყო ჭამისადმი მისი არცთუ დადებითი დამოკიდებულებით. თუ მაინცდამაინც იძულებული იყო ეჭამა, ამას ისეთი გამომეტყველებით აკეთებდა, რომ მის მაცქერალ ადამიანს სიბრალული იპყრობდა J. თუმცა, ბუნება მაინც თავისას ითხოვს და ორგანიზმს დროდარო კვება სჭირდება. ერთ დღესაც ბაქარი სახლში მარტო იყო და მეცადინეობით გართულს ჭამა არც მოჰგონებია, მაგრამ საღამოს შიმშილის გრძნობამ მაინც შეაწუხა და მაცივარს მიაშურა იმ იმედით, რომ რაიმე მის შესაფერის საკბილოს იპოვიდა. რამდენად დიდი იყო მისი გაოცება, როდესაც მაცივრის კარი გამოაღო და შიგ ჩვეულებრივი საჭმელი კი არა, სტრიქონი დახვდა! ამასთან, ჩვეულებრივი სტრიქონი კი არა, არამედ „ბუბლიკივით“ მრგვალი. ცნობისმოყვარე ბაქარი სტრიქონმა იმდენად დააინტერესა, რომ საჭმელი სულ დაავიწყდა და ხელში კრიალოსანივით მისი მარცვლა დაიწყო. მაგალითად, თუ ამ სტრიქონს ექნებოდა სახე: abacaba, მაშინ მარცვლის (წრეზე ტრიალის) შედეგად მისგან შეიძლება მივიღოთ სტრიქონები:

·         abacaba

·         bacabaa

·         acabaab

·         cabaaba

·         abaabac

·         baabaca

·         aabacab

            თუმცა ბაქარს ცოტა ხანში ისევ შიმშილმა შეახსენა თავი, მაცივარში კი ცნობილი სტრიქონის გარდა არაფერი იყო. უცებ მან ჩაიფიქრა, რომ თუ შესძლებს დათვალოს, მარცვლის პროცესში რამდენჯერ მიიღება ლექსიკოგრაფიულად მინიმალური სტრიქონი, მაშინ მაგიური ძალები მაცივარში მისთვის ასე თუ ისე მისაღებ საჭმელს გააჩენენ. დაეხმარეთ მას ამის დადგენაში.

            უფრო ფორმალურად: მოცემულია სტრიქონი. n სიგრძის მქონე s სტრიქონის ციკლური წანაცვლება ეწოდება სტრიქონს, რომელიც მიიღება საწყისი სტრიქონიდან პირველი k (0≤k<n) რაოდენობის სიმბოლოს მოცილებით და მათი ბოლოში მიწერით.

            დაწერეთ პროგრამა, რომელიც დათვლის, რამდენჯერ შეგვხვდება ლექსიკოგრაფიულად მინიმალური ციკლური წანაცვლება მოცემული სტრიქონის ყველა ციკლურ წანაცვლებებს შორის.    

შესატანი მონაცემები: სტანდარტული შეტანის ერთადერთ ტრიქონში მოცემულია ბაქარის მიერ მაცივარში ნაპოვნი S სტრიქონი. ის ცარიელი არ არის, შედგება პატარა ლათინური ასოებისაგან და მისი სიგრძე არ აღემატება 10 000 000-ს.

გამოსატანი მონაცემები: სტანდარტული გამოტანის ერთადერთ სტრიქონში უნდა ჩაიწეროს ერთი მთელი რიცხვი - მინიმალურ ციკლურ წანაცვლებათა საძიებელი  რაოდენობა.

ტესტების 20%-ში  |S|≤102;

ტესტების 20%-ში  |S|≤104;

ტესტების 20%-ში  |S|≤105.




მაგალითები

შესატანი მონაცემები
aaaa დაკოპირება
გამოსატანი მონაცემები
4 დაკოპირება
შესატანი მონაცემები
abacaba დაკოპირება
გამოსატანი მონაცემები
1 დაკოპირება

შენიშვნა

პირველ ტესტში მინიმალურ ციკლურ წანაცვლებას წარმოადგენს სტრიქონი aaaa, ხოლო მეორე ტესტში კი - სტრიქონი aabacab.