문자열 접기

면접 대비

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

요약

3(AB)와 같은 반복 표기를 사용해 주어진 대문자 문자열로 펼쳐지는 가장 짧은 접힌 문자열의 길이를 구한다.

문제

Bill은 'A'부터 'Z'까지의 대문자로만 이루어진 문자열에서 반복되는 부분을 접어 더 짧게 표현하려고 한다. 예를 들어 문자열 AAAAAAAAAABABABCCD는 10(A)2(BA)B2(C)D로 표현할 수 있다.

접힌 문자열(folded sequence)과 이를 펼치는(unfolding) 규칙은 다음과 같이 정의된다.

'A'부터 'Z'까지의 문자 하나로 이루어진 문자열은 접힌 문자열이다. 이 문자열을 펼치면 그 한 글자 자신이 된다.
$S$ 와 $Q$ 가 접힌 문자열이면 $SQ$ 도 접힌 문자열이다. $S$ 가 $S'$ 로 펼쳐지고 $Q$ 가 $Q'$ 로 펼쳐지면, $SQ$ 는 $S'Q'$ 로 펼쳐진다.
$S$ 가 접힌 문자열이면 $X(S)$ 도 접힌 문자열이며, 여기서 $X$ 는 1보다 큰 정수의 십진 표기이다. $S$ 가 $S'$ 로 펼쳐지면 $X(S)$ 는 $S'$ 를 $X$ 번 반복한 문자열로 펼쳐진다.

주어진 문자열을 접어서 만들 수 있는 접힌 문자열 중, 글자 수가 가장 적은 것의 글자 수를 구하여라.

'A'부터 'Z'까지의 대문자로 이루어진 문자열 한 줄이 주어진다. 문자열의 길이는 1 이상 100 이하이다.

입력 문자열로 펼쳐지는 접힌 문자열 중, 글자 수가 가장 적은 것의 글자 수를 정수 하나로 출력한다.