Problem: dp3
You're working for a company creating a new text compression program. You've been assigned the task of creating an algorithm that will give an estimate, before the compression program itself runs, how good a job that compression program will be able to do.
The compression algorithm works by taking a string, and finding any repeating sections, and replacing those repeating sections with just one copy (and noting how many copies of that section to produce). For example, the string AAAGH!!! can be expressed as (A)3GH(!)3 while the string WOOFWOOFMEOWMEOW can be written as (W(O)2F)2(MEOW)2. Your job is to take any input string and determine the smallest number of letters needed to rewrite it in this way (disregarding the notation describing the number of repetitions, and the added brackets).
Input
The input will consist of a sequence of test cases, one per line. Each test case consists of a single string of characters. Input will be restricted to alphanumeric text (upper and lower case), as well as spaces, colons, exclamation marks, periods, commas, question marks, and semicolons (:!.,?;).
Bounds
Input strings will be between 1 and 90 characters.
Output
For each test case, output an integer that is the length of the smallest string you can achieve with this compression algorithm, excluding the extra notation added to describe how to compress the string.
Sample Input
AAAGH!!! WOOFWOOFMEOWMEOW 3.14159Help! Help! I'm trapped in a universe factory!71214
Sample Output
4 7 51