Question

最长公共子序列算法求破！杭电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);
}
}

Answer 1

有标准的算法，采用动态规划

Answer 2

同上啊，是的