Минимальный период

시간 제한6초메모리 제한1024 MB

요약

어딘가에 문자가 정확히 하나 더 삽입된 문자열이 주어질 때, 반복과 접두사로 만들어졌을 원래 메시지의 최소 길이를 구한다.

난이도: 보통10점 중 7점
유형: 문자열, 문자열 매칭, 이분 탐색, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Для передачи сообщений отряд Китнисс использует свою уникальную шифровку. Шифровка представляет собой повторение сообщения некоторое ненулевое число раз и дописывание префикса (возможно, пустого) исходного сообщения в конец шифровки. Например, сообщение <<hello>> можно закодировать как <<hellohellohell>>, как <<hellohellohe>>, а также например как <<hellohellohello>>.

Недавно Китнисс получила зашифрованное сообщение и сразу поняла, что с ним что-то не так. Видимо, при передаче возникла какая-то ошибка и в где-то добавился лишний символ. Теперь Китнисс хочет понять, каким же все-таки было исходное сообщение, но так как точно сейчас сказать это невозможно, она хочет узнать минимальную длину сообщения, которое могло быть закодировано. Например, если Китнисс получила зашифрованное сообщение <<abadbab>>, она может понять, что в середине сообщения есть лишний символ <<d>> и минимальная длина закодированного сообщения равна 2.

입력

В единственной строке находится непустая строка из строчных латинских букв, длина которой хотя бы 2 и не превосходит $10^6$ .

출력

В единственной строке выведите минимальную длину сообщения.

예제3

예제 1
입력
```
abba
```
예상 출력
```
2
```
예제 2
입력
```
abadbab
```
예상 출력
```
2
```
예제 3
입력
```
daaa
```
예상 출력
```
1
```