![]() |
![]() ![]() | |||
|
![]() | |||
![]() | Task: Periods of WordsAvailable memory: 32 MBA 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 0 letters.
By A = BC we denotes that A is a string obtained by concatenation (joining by writing one immediately after another, i.e. without any space, etc.)
of the strings B and C (in this order).
A string P is a prefix of the string A, if there is
a string B, that A = PB.
In other words, prefixes of A are the initial fragments of A.
In addition, if P A string Q is a period of A, if Q is a proper prefix of A and A is a prefix (not necessarily a proper one) of the string QQ. For example, the strings abab and ababab are both periods of the string abababa. The maximum period of a string A is the longest of its periods or the empty string, if A doesn't have any period. For example, the maximum period of ababab is abab. The maximum period of abc is the empty string.
TaskWrite a programme that:
InputIn the first line of the standard input there is one integer k ( 1![]() ![]()
OutputIn 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.
ExampleFor the following input data:8 babababathe correct answer is: 24 ![]() Print friendly version |