首页 > 代码库 > Uva 1630 折叠串
Uva 1630 折叠串
题目链接：https://uva.onlinejudge.org/external/16/1630.pdf
题意：折叠串，给一个字符串，相同部分可以折叠，折叠可以嵌套。求最短长度的一种折叠方法。括号和数字的长度也要考虑进去。
刚看到这个题目，没有一点思路，还是大牛们厉害！
分析：一个串，可以转成两种形式，要么本身可以转成有重叠部分的串，要么分成两个部分，再转成有重叠部分的串。
本身是否是重叠串，利用kmp查，分成两个部分，遍历一遍所有情况，这样，dp顺序就出来了，最外层是每次查的长度，第二层就是，利用这个长度，从每一个点开始查起。状态描叙是d[i][j]从 i 到 j 的最短字符串。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 100 + 10; 5 6 string d[maxn][maxn]; 7 char s[maxn],t[maxn]; 8 9 10 11 int f[maxn];12 13 string ToString(int x)14 {15 string ans = "";16 while(x)17 {18 ans +=(char)(‘0‘+(x%10));19 x/=10;20 }21 reverse(ans.begin(),ans.end());22 return ans;23 }24 25 void getFail(char* s)26 {27 int len = strlen(s);28 f[0] = f[1] = 0;29 for(int i=1; i<len; i++)30 {31 int j = f[i];32 while(j&&s[i]!=s[j])33 j = f[j];34 f[i+1] = s[i]==s[j] ? j+1:0;35 }36 }37 38 int main()39 {40 while(scanf("%s",s)!=EOF)41 {42 int len = strlen(s);43 for(int i=0; i<len; i++)44 d[i][i] = string("")+s[i];45 46 47 for(int l=2; l<=len; l++)48 {49 for(int i=0; i + l - 1 < len; i++)50 {51 int j = i + l - 1;52 d[i][j] = "";53 for(int k=i; k<=j; k++)54 {55 d[i][j] +=s[k];56 t[k-i] = s[k];57 }58 59 t[j-i+1] = 0;60 getFail(t);61 if(l%(l-f[l])==0) //自身是重复的62 {63 int cycle = l - f[l];64 string t = "";65 t = ToString(l/cycle);66 t+=‘(‘;67 t+=d[i][i+cycle-1];68 t+=‘)‘;69 if(t.length()<d[i][j].length()) d[i][j] = t;70 }71 72 for(int k=i; k<j; k++)73 {74 if(d[i][k].length()+d[k+1][j].length()<d[i][j].length())75 {76 d[i][j] = d[i][k] + d[k+1][j];77 }78 }79 }80 }81 cout<<d[0][len-1]<<endl;82 }83 return 0;84 }
Uva 1630 折叠串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。