სიტყვის პერიოდი

დროის ლიმიტი: 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 დაკოპირება