首页 > 代码库 > NYOJ 661 亲亲串

NYOJ 661 亲亲串

亲亲串

时间限制:1000 ms  |  内存限制:65535 KB
难度:3
描述

如果有一个字符串,它的前半段等于它后半段,例如 abcabc,我们就叫这种字符串为“亲亲串”。

现在给你一个字符串(仅有大小写字母组成),可以在任意的位置添加任意个字符,使这个字符串成为一个“亲亲串”,最少需要添加多少个字符?

输入
第一行是一个整数N(0<N<=1000),表示有N组测试数据。
接下来有N行,每行有一个字符串,字符串的长度小于1000;
输出
对于每组测试数据输出一个整数,为最小添加字符数
样例输入
3
abcbc
aaaab
abcd
样例输出
1
1
4
错误代码!不知道为什么提交不成功,请路过大神指点!
#include<stdio.h>
#include<string.h>
char str[1005],stack1[1005],stack2[1005];
int main()
{
	int T,i,j,count,top1,top2;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",str);
		count=top1=top2=0;
		memset(stack1,0,sizeof(stack1));
		memset(stack2,0,sizeof(stack2));
		for(i=0;str[i]!=‘\0‘;i++)
		{
			if(top1==top2)
			{
				stack1[top1]=str[i];
				top1++;
			}
			else
			{
				for(j=top2;j<top1;j++)
				{
					if(str[i]==stack1[j])
					{
						count+=(j-top2);
						stack2[j]=str[i];
						top2=j+1;
						break;
					}
				}
				if(j>=top1)
				{
					stack1[top1]=str[i];
					top1++;
				}
			}
		}
		count+=(top1-top2);
		printf("%d\n",count);
	}
	return 0;
}

AC码:
#include<stdio.h>
#include<string.h>
char str[1005];
int dp[1005],len;
int fun(int t)
{
	int i,j,a,b;
	memset(dp,0,sizeof(dp));
	for(i=0;i<t;i++)
	{
		a=0;
		for(j=t;j<len;j++)
		{
			b=dp[j+1];
			if(str[i]==str[j])
				dp[j+1]=a+1;
			else if(dp[j]>dp[j+1])
				dp[j+1]=dp[j];
			a=b;
		}
	}
	return dp[len];
}
int main()
{
	int T,i,max,t;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",str);
		len=strlen(str);
		max=fun(len/2);
		if(max==len/2)
		{
			printf("%d\n",len-2*max);
			continue;
		}
		for(i=max;i+max<len;i++)
		{
			t=fun(i);
			if(t>max)
				max=t;
		}
		printf("%d\n",len-2*max);
	}
	return 0;
}