| Fişierul intrare/ieşire: | kalindrome.in, kalindrome.out | Sursă | IIOT 2021-22 Runda 2 |
| Autor | William Di Luigi | Adăugată de |  Stefan Dascalescu •stefdascalescu |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Kalindrome
William loves strings and their properties, and he is especially fond of palindromes. He likes palindromes so much, that he started reading lots of research papers on them and finally stumbled upon a new kind of property that generalizes the palindrome concept: the kalindrome.
We say that a string is a kalindrome if, for some positive integer K, it's possible to split the string in many substrings, each of them K characters long, so that they can be read from left to right in the same way as right to left. More precisely: if we concatenate the substrings starting from the last one, we will recreate the original string.
For example: the word banaba is a kalindrome, because if we choose K=2 then we obtain the substrings: ba, na, ba, which can indeed be concatenated starting from the last one, to reconstruct the original word.
You might have noticed that, by this definition, any string is a kalindrome! That's true, in fact we could choose K to be equal to the string's length, and we would then obtain a single substring which would of course respect the definition! However, William is interested to know what's the smallest K for a given string that would prove it is a kalindrome.
Help him by writing a program that automates this test!
Date de intrare
The input file kalindrome.in contains the only integer N, 1 ≤ N ≤ 10^6, the length of the string to be tested. The second line contains a string S, consisting of lowercase letters.
Date de ieşire
You will need to write in the output file kalindrome.out a single line with an integer: the smallest positive integer K that proves the kalindromeness of the string S.
Restricţii
- For tests worth 40 points, K is either 1 or N.
- For tests worth 40 more points, 1 ≤ N ≤ 1000.
- The scores obtained now may be different compared to the ones from the original contest
Exemplu
| kalindrome.in | kalindrome.out |
|---|---|
| 6 banaba | 2 |
| kalindrome.in | kalindrome.out |
|---|---|
| 12 eszyciyciesz | 3 |
Explicaţie
In the first sample case, we can split the string in three 2-characters long substrings: ba, na, ba.
In the second sample case, we can split the string in four 3-characters long substrings: esz, yci, yci,
esz.
