Sözlərin dövrləri
Rəqəm P, rəd A-nın prefiksi adlanır, əgər A=PB bərabərliyi ödənilirsə, burada P və ya B boş ola bilər. Rəqəm P, qeyri-trivial prefiks adlanır, əgər A=PB bərabərliyi ödənilir və həm P, həm də B boş deyilsə. Rəqəm Q, rəd A-nın periodu adlanır, əgər Q, A-nın qeyri-trivial prefiksidirsə və A, QQ rədinin prefiksi olursa (bu prefiks qeyri-trivial olmaq məcburiyyətində deyil). Məsələn, abab və ababab rədiləri abababa rədinin periodlarıdır.
Maksimal period, rəd A-nın ən uzun periodudur və ya A-nın heç bir periodu yoxdursa, boş rəd kimi qəbul edilir. Məsələn, ababab rədinin maksimal periodu abab, abc rədinin maksimal periodu isə boş rəd kimi qəbul edilir.
Verilmiş A rədinin bütün prefiksləri üçün maksimal periodların uzunluqlarının cəmini hesablayan bir proqram yazın.
Giriş verilənləri
Giriş faylının ilk sətirində bir tam ədəd k (1 ≤ k ≤ 1000000) – A rədinin uzunluğu verilir. İkinci sətirdə k kiçik ingilis əlifbası hərflərindən ibarət ardıcıllıq – A rədidir.
Çıxış verilənləri
Çıxış faylının tək sətirində hər bir A prefiksinin maksimal periodlarının uzunluqlarının cəmini verin.