W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
A string is a finite sequence of lower-case (non-capital) letters of the English alphabet. Particularly, it may be an empty sequence, i.e. a sequence of letters. By we denotes that is a string obtained by concatenation (joining by writing one immediately after another, i.e. without any space, etc.) of the strings and (in this order). A string is a prefix of the string , if there is a string , that . In other words, prefixes of are the initial fragments of . In addition, if and is not an empty string, we say, that is a proper prefix of .
A string is a period of , if is a proper prefix of and is a prefix (not necessarily a proper one) of the string . For example, the strings abab and ababab are both periods of the string abababa. The maximum period of a string is the longest of its periods or the empty string, if doesn't have any period. For example, the maximum period of ababab is abab. The maximum period of abc is the empty string.
Write a programme that:
In the first line of the standard input there is one integer () - the length of the string. In the following line a sequence of exactly lower-case letters of the English alphabet is written - the string.
In the first and only line of the standard output your programme should write an integer - the sum of lengths of maximum periods of all prefixes of the string given in the input.
For the input data:
8 babababa
the correct result is:
24
Task author: Szymon Acedanski.