주기 문자열

면접 대비

시간 제한2초메모리 제한512 MB

요약

문자열이 주어질 때, 길이 k의 블록으로 나눴을 때 각 블록이 이전 블록을 한 칸 회전한 형태가 되는 가장 작은 k를 구한다.

난이도: 보통10점 중 4점
유형: 문자열, 완전 탐색, 구현, 수학
정답자: 아직 제출이 없습니다

문제

$k$ -주기 문자열을 다음과 같이 정의한다.

문자열 $s$ 의 길이 $|s|$ 가 $k$ 의 배수이고, $s$ 를 길이가 $k$ 인 $|s|/k$ 개의 조각으로 자를 때 첫 조각을 뺀 모든 조각이 바로 앞 조각의 마지막 글자를 맨 앞으로 옮긴 문자열과 같으면, $s$ 를 $k$ -주기 문자열이라고 한다.

예를 들어 abccabbcaabc는 $3$ -주기 문자열이다. 이 문자열은 abc, cab, bca, abc로 잘리고, 첫 조각을 뺀 각 조각은 앞 조각을 한 글자씩 회전시킨 결과다 (abc $\rightarrow$ cab, cab $\rightarrow$ bca, bca $\rightarrow$ abc).

문자열 $s$ 가 주어질 때, $s$ 가 $k$ -주기 문자열이 되는 가장 작은 $k$ 를 구하라.

입력

첫째 줄에 소문자로만 이루어진 문자열 $s$ 가 주어진다 ( $1 \leq |s| \leq 100$ ).

출력

입력 문자열이 $k$ -주기 문자열이 되는 가장 작은 $k$ 를 한 줄에 출력한다.

예제4

예제 1
입력
```
aaaaaaaa
```
예상 출력
```
1
```
예제 2
입력
```
abbaabbaabba
```
예상 출력
```
2
```
예제 3
입력
```
abcdef
```
예상 출력
```
6
```
예제 4
입력
```
abccabbcaabc
```
예상 출력
```
3
```