hdu 1159感觉算法没错就是过不了求解

lee_jun 发布于 2013/05/08 19:37
阅读 75
收藏 0

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=1159

/*

输入s1和s2两个字符串比较他们相同子串的长度
用s2去匹配s1,将s1作为字典;
设i为[0,s2.length)区间中的某个值。
f(i)为含字母s2[i]的最大公共字串中的元素个数;
a[i]记录s2[i]字符在s1中出现的位子;
b[i]存放每次f(i)生成的长度;
f(i)=max{f(j)|0<=j<i AND s2[i]存在于s1(a[j]+1,s1.length-1)}+1;
取出f(i)中的最大值就是我们要的结果
*/
#include<stdio.h>
#include<string.h>
char s1[600],s2[600];
int l1,l2;
int a[600],b[600];
int Max=0;
int f(int i)
{
	int j,max=0,p=0,k;
	if(strchr(s1,s2[i]))
	{
		for(j=0;j<l1;j++)
		{
			if(s2[i]==s1[j]) break;
		}
		p=j;
		for(j=0;j<i;j++)
		{
			if(strchr(&s1[a[j]+1],s2[i])&&b[j]>max)
			{
				max=b[j];
				for(k=a[j]+1;k<l1;k++)
				{
					if(s1[k]==s2[i])
					{
						p=k;
						break;
					}
				}
			}
		}
		b[i]=max+1;
		if(b[i]>Max) Max=b[i];
		a[i]=p;
	}
	else
	{
		a[i]=-1;
		b[i]=0;
	}
}
int main()
{
	int i;
	//freopen("input.txt","r",stdin);
	while(scanf("%s %s",s1,s2)!=EOF)
	{
		Max=0;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		l1=strlen(s1);		//计算s1,s2的长度
		l2=strlen(s2);
		for(i=0;i<l2;i++)
		{
			f(i);
		}
		printf("%d\n",Max);
	}
}
加载中
返回顶部
顶部