10
22
2015
1

【KMP+DP】 ZHOJ模拟赛34 T1压缩

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;
} 
Category: 魔泥赛 | Tags: KMP DP | Read Count: 851
jcvb 说:
2015年10月23日 09:19

%%%字符串小能手


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com