문자열 압축하기

어떤 문자열에서 특정한 패턴이 반복되면, 그 반복을 이용해 문자열을 더 짧게 표현할 수 있다. 이런 방법을 압축 기법이라고 한다. RLE(Run Length Encoding)는 가장 기본적인 압축 방법으로, 같은 문자가 여러 번 반복될 때 문자를 한 번만 쓰고 반복 횟수를 함께 적는다. 예를 들어 abccddd는 abc2d3처럼 표현할 수 있다.

문자 하나 대신 문자열 단위를 사용하면 RLE를 더 확장할 수 있다. 주어진 문자열에서 어떤 문자열 S가 k번 연속으로 반복되면 이를 k(S)로 표현할 수 있다. 예를 들어 letsgogogo는 lets3(go)로 압축할 수 있고, 이 표현의 길이는 9이다. 압축된 길이를 계산할 때는 괄호와 반복 횟수 k를 나타내는 숫자의 길이도 모두 포함한다.

압축은 중첩해서 사용할 수 있다. 예를 들어 nowletsgogogoletsgogogo는 now2(lets3(go))로, nowletsgogogoletsgogogoandrunrunrun은 now2(lets3(go))and3(run)으로 압축할 수 있다. 이 확장된 방법에서는 문자 반복을 abc2d3처럼 쓸 수 없으며, 같은 뜻이라면 ab2(c)3(d)처럼 문자열 반복 표기만 사용해야 한다.

문자열이 주어졌을 때 만들 수 있는 압축 표현 중 가장 짧은 표현의 길이를 구하시오. 압축하지 않는 것도 가능한 표현이다.

첫째 줄에 알파벳 소문자로만 이루어진 문자열이 주어진다. 문자열은 공백 없이 주어지며, 길이는 200자를 넘지 않는다.

첫째 줄에 가능한 압축 표현의 최소 길이를 출력한다. 압축하지 않는 편이 더 짧거나 같은 경우에는 원래 문자열의 길이를 출력한다.