11022

This is a dp problem where kmp algorithm(specially prefix function)  is used to solve the problem.

If a string is multiple of a repeated string then the difference between the string length and last index of the prefix table indicates the minimal length of the repeated string. A brief and nice discussion is available here .

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

#define INF 100000000
using namespace std;

int dp[85][85];
int lps[85];
string s;
int prefix_function(string str)
{
	memset(lps,0,sizeof(lps));
	int len = 0;
	int i=1;
	lps[0]=0;
	int length = str.size();
	while(i<length)
	{
		if(str[i]==str[len])
		{
			len+=1;
			lps[i]=len;
			i+=1;
		}
		else
		{
			if(len!=0)
			{
				len = lps[len-1];
			}
			else
			{
				len = 0;
				i+=1;
			}
		}
	}
	int minimal_lengthOf_repeated_str = str.size()-lps[str.size()-1];
	int times = str.size()/minimal_lengthOf_repeated_str;
	if(str.size()==times*minimal_lengthOf_repeated_str)
	return minimal_lengthOf_repeated_str;
	else
	return str.size();
}

int DP(int left,int right)
{
	if(left==right)
	return 1;
	if(dp[left][right]!=-1)
		return dp[left][right];
	string str1 = s.substr(left,right-left+1);
	int val = prefix_function(str1);
	int ans1,ans2;
	if(val==right-left+1)
	{
		int mn = INF;
		for(int i=left;i<right;i++)
		{
			ans1 = DP(left,i);
			ans2 = DP(i+1,right);
			mn = (mn<(ans1+ans2)?mn:(ans1+ans2));
		}
		dp[left][right]=mn;
	}
	else
	{
		dp[left][right] = DP(left,left+val-1);
	}
	return dp[left][right];
}

int main()
{
	while(cin>>s)
	{
		if(s=="*")
		break;
		memset(dp,-1,sizeof(dp));
		printf("%d\n",DP(0,s.size()-1));
	}
	return 0;
}