一个字符串如果能简写,要么是重复多次,按题中的要求简写;要么是左右两个部分分别简写后再拼起来。
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 ;
}
代码君