주기 접두사
시간 제한2초메모리 제한128 MB
문자열의 각 접두사에 대해 어떤 부분 문자열을 n번 반복한 형태인지 확인하고, 가능한 가장 큰 n을 구하는 문제입니다.
문제
문자열 X를 n번 이어 붙인 문자열을 (X)^n으로 나타낸다. 예를 들어 (ab)^3은 ababab이다.
어떤 문자열 Y가 (X)^n 꼴로 표현될 수 있고 n > 1이라면, Y를 주기적인 문자열이라고 한다. 예를 들어 ab는 주기적인 문자열이 아니지만, abab는 (ab)^2로 표현할 수 있으므로 주기적인 문자열이다.
알파벳 소문자로만 이루어진 문자열 S가 주어진다. S의 앞에서부터 i개의 문자로 이루어진 접두사가 주기적인 문자열이 되는 모든 경우를 찾아야 한다. 한 접두사를 여러 가지 방법으로 표현할 수 있다면, 반복 횟수 n이 가장 큰 표현을 선택한다.
가능한 모든 (i, n) 쌍을 구하는 프로그램을 작성하시오.
제한:
2 <= |S| <= 1,000,000S는 알파벳 소문자로만 이루어져 있다.
입력
첫째 줄에 문자열 S가 주어진다.
출력
i가 증가하는 순서대로, 조건을 만족하는 i와 그때의 최대 반복 횟수 n을 한 줄에 하나씩 출력한다.