1397: 【NOIP2014模拟赛No.34】压缩
时间限制: 1 Sec 内存限制: 512 MB
题目描述
我们定义一种压缩方法。首先将字符串分成若干个部分。对于每个部分，我们找出其最短的循环节。每个部分的循环节拼起来就是压缩后的字符串。
给定一个字符串，长度为n。请求出这个字符串可以被压缩成的最短长度。
输入
输入数据仅有一行，包含一个字符串。保证字符串只含有小写英文字母。
输出
输出一行，包含一个整数，代表答案。
样例输入
bababacacac
样例输出
5
提示
一种可行的方法是 bababa|c|acac，压缩后得到 bacac，长度为 5。
对于 20%的数据，n≤10。
对于 40%的数据，n≤100。
对于 80%的数据，n≤1000。
对于 100%的数据，n≤5000。
选拔爆0，233333333
听字符串大师ZNZ讲解以后突然想来水一发
N^3传统DP大概随手写吧= =（你为何爆零←_←）
KMP：失配指针，网上讲义太多辣。
应用：当N[i]%(i-N[i])=0表示S[1..i]是一个完整的循环节。
用这个优化一下大概就N^2水过去了。
Code：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#define maxn 5010
using namespace std;
int N[maxn];
void KMP(char P[])
{
memset(N,0,sizeof(N));
int L=strlen(P);
for (int i=1;i<L;i++)
{
int j=N[i];
while (j&&P[i]!=P[j])
j=N[j];
N[i+1]=(P[i]==P[j])?j+1:0;
}
}
int f[maxn];
int main()
{
char S[maxn];
memset(f,0x7f7f7f7f,sizeof(f));
f[0]=0;
scanf("%s",S);
int l=strlen(S);
for (int i=0;i<l;i++)
{
KMP(S+i);
for (int j=i+1;j<=l;j++)
if (N[j-i]%(j-i-N[j-i])==0&&f[j]>f[i]+j-i-N[j-i])
f[j]=f[i]+j-i-N[j-i];
}
printf("%d",f[l]);
return 0;
}
2015年10月23日 09:19
%%%字符串小能手