라디오 전송
면접 대비시간 제한1초메모리 제한128 MB
반복 송출된 문자열의 부분 수신본이 주어질 때, KMP 실패 함수를 이용해 가장 짧은 반복 단위의 길이를 구합니다.
문제
라디오 방송국은 하나의 메시지를 여러 청취자에게 전송한다. 모든 청취자가 메시지를 확실히 받을 수 있도록, 방송국은 같은 메시지를 끊임없이 이어 붙여 반복해서 전송한다.
한 청취자가 받은 문자열 S가 주어진다. 청취자가 받은 문자열의 길이는 항상 방송국이 실제로 보낸 원본 메시지의 길이보다 크거나 같다. 이때 방송국이 보낸 원본 메시지를 구하는 프로그램을 작성하라.
즉, 문자열 S가 주어졌을 때, S가 S′ + S′ + ⋯ + S′(S′를 여러 번 이어 붙인 문자열)의 부분 문자열이 되도록 하는 가장 짧은 문자열 S′를 찾아 그 길이를 출력하면 된다.
입력
첫째 줄에 S의 길이 L이 주어진다. 둘째 줄에 길이가 L인 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있다. (1 ≤ L ≤ 1,000,000)
출력
첫째 줄에 가장 짧은 원본 메시지 S′의 길이 L′을 출력한다.
힌트
예를 들어 S가 cabcabca이면 가능한 원본 메시지로 cab, abc, abcabc 등이 있으며, 길이가 3보다 짧은 메시지는 존재하지 않는다. 따라서 답은 3이다.