დროის ლიმიტი: 2 წმ
მეხსიერების ლიმიტი: 64 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
წყარო: პოლონეთი, ოლიმპიადა 13, ეტაპი 1
სტრინგი წარმოადგენს სასრულ მიმდევრობას ინგლისური ანბანის. ის, ასევე, შეიძლება იყოს ცარიელი მიმდევრობა, ანუ 0 ცალი ასოს მიმდევრობა. A=BC გულისხმობს, რომ A მიღებულია B-ს და C-ს კონკატენაციით (მიწებებით). სტრინგი P პრეფიქსია A-სი, თუ არსებობს სტრინგი B ისეთი, რომ A=PB. სხვა სიტყვებით რომ ვთქვათ, A-ს პრეფიქსები A-ს დასაწყისს წარმოადგენს. დამატებით, თუ P არ უდრის A-ს და P არაცარიელია, ვამბობთ, რომ P სათანადო პრეფიქსია A-სი.
სტრინგი Q პერიოდია A-სი, თუ Q სათანადო პრეფიქსია A-სი და A პრეფიქსია QQ-სი. მაგალითად, სტრინგები abab და ababab ორივე პერიოდია abababa-სი. მაქსიმალური პერიოდი A-სი არის ყველაზე გრძელი სტრინგი მისი პერიოდებიდან ან ცარიელი სტრინგი თუ A-ს არ გააჩნია პერიოდი. მაგალითად, მაქსიმალური პერიოდი ababab-სი არის abab, ხოლო მაქსიმალური პერიოდი abc-სი არის ცარიელი სტრინგი.
დაწერეთ პროგრამა, რომელიც:
შესატანი მონაცემები: პირველ ხაზზე რიცხვი ( ) - სტრინგის სიგრძე. მომდევნო ხაზზე მიმდევრობა k პატარა ასოსი (lowercase) ინგლისური ანბანის, ანუ პატარა ასოებისგან შემდგარი სტრინგი.
გამოსატანი მონაცემები: პირველ და ერთადერთ ხაზზე თქვენმა პროგრამამ უნდა გამოიტანოს რიცხვი, რომელიც იქნება ყველა შესაძლო პრეფიქსის მაქსიმალური პერიოდების ჯამი.
შესატანი მონაცემები
8 babababa დაკოპირება
გამოსატანი მონაცემები
24 დაკოპირება