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 .
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#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; } |