UVa 11022

#include <bits/stdc++.h>

using namespace std;

#define Max 80

int dp[Max][Max];
char s[Max];

int dfs(int begin, int end) {

    if(begin == end)
        return 1;

    if(dp[begin][end])
        return dp[begin][end];

    int ret = INT_MAX;

    for(int i = begin; i < end; i++)
        ret = min(ret, dfs(begin, i) + dfs(i + 1, end));

    for(int i = 1, length = end - begin + 1; i <= length; i++) {
        if(length % i == 0) {
            int k = begin, j = 0;
            for(; k <= end; k++) {
                if(s[k] != s[j + begin])
                    break;
                ++j;
                if(j >= i)  j = 0;
            }
            if(k == end + 1 and end != begin + i - 1)
                ret = min( ret, dfs(begin, begin + i - 1) );
        }
    }
    return dp[begin][end] = ret;
}

int main(void) {
    while(~scanf("%s", s)) {
        if( !strcmp(s, "*") )
            break;
        memset(dp, 0, sizeof dp);
        int len = strlen(s);
        printf( "%d\n", dfs(0, len - 1) );
    }
    return 0;
}