UVa 1630 区间DP Folding

一个字符串如果能简写，要么是重复多次，按题中的要求简写；要么是左右两个部分分别简写后再拼起来。

dp(i, j)表示字串(i, j)所能被简写的最短的字符串。

判断一个字符串是否为周期串以及求出它的周期用的KMP算法。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <string>

 using namespace std;

 const int maxn =  + ;

 char s[maxn], t[maxn];

 string d[maxn][maxn];

 string ToString(int x)

 {

     string ans = "";

     while(x)

     {

         ans += (char) ('' + (x % ));

         x /= ;

     }

     reverse(ans.begin(), ans.end());

     return ans;

 }

 int f[maxn];

 void getFail(char* s)

 {

     int len = strlen(s);

     f[] = f[] = ;

     for(int i = ; i < len; i++)

     {

         int j = f[i];

         while(j && s[i] != s[j]) j = f[j];

         f[i+] = s[i] == s[j] ? j+ : ;

     }

 }

 int main()

 {

     while(scanf("%s", s) == )

     {

         int len = strlen(s);

         for(int i = ; i < len; i++) d[i][i] = string("") + s[i];

         for(int l = ; l <= len; l++)

         {

             for(int i = ; i + l -  < len; i++)

             {

                 int j = i + l - ;

                 d[i][j] = "";

                 for(int k = i; k <= j; k++) { d[i][j] += s[k]; t[k-i] = s[k]; }

                 t[j - i + ] = ;

                 getFail(t);

                 if(l % (l - f[l]) == )

                 {

                     int cycle = l - f[l];

                     string t = "";

                     t = ToString(l / cycle);

                     t += '(';

                     t += d[i][i + cycle - ];

                     t += ')';

                     if(t.length() < d[i][j].length()) d[i][j] = t;

                 }

                 for(int k = i; k < j; k++)

                 {

                     if(d[i][k].length() + d[k+][j].length() < d[i][j].length())

                         d[i][j] = d[i][k] + d[k+][j];

                 }

             }

         }

         cout << d[][len - ] << endl;

     }

     return ;

 }

代码君