레이팅 미적용설명
문자열 \(S\) 가 주어진다. \(S\) 를 만들어 내는 가장 짧은 주기(period) 의 길이를 구하여라.
길이 \(p\) 가 \(S\) 의 주기라는 것은, 모든 \(i\) (\(1 \le i \le |S|\))에 대해 \(S_i = S_{i-p}\) 가 성립함(\(i>p\) 일 때)을 의미한다. 즉 \(S\) 의 앞쪽 길이 \(p\) 패턴이 \(S\) 전체에 걸쳐 반복된다(마지막 반복은 잘릴 수 있다). 답으로는 이러한 \(p\) 중 최솟값을 출력한다.
제약
\(1 \le |S| \le 1{,}000{,}000\)
\(S\) 는 알파벳 소문자로만 이루어져 있다.
입력 형식
첫째 줄에 알파벳 소문자로 이루어진 문자열 \(S\) 가 주어진다.
출력 형식
\(S\) 의 최소 주기의 길이를 출력한다.
예제 1
입력
abcabcab
출력
8설명
abcabcab 는 abc 가 반복되어 만들어진다. 마지막 ab 처럼 잘려도 주기로 인정되므로 최소 주기는 3이다.
예제 2
입력
abcabcabc
출력
3설명
abcabcabc 도 abc 의 반복이므로 최소 주기는 3이다.
문제 시리즈
문제 정보
riseoj 작성
출처 Original
태그