文章
39
粉丝
74
获赞
1
访问
20.4k
#include <stdio.h>
#include <stdlib.h>
int m,n;
char s1[105],s2[105];
int dp[105][105];
int max1(int a,int b)
{
if(a>=b)return a;
else return b;
}
int main()
{
while(scanf("%s%s",s1,s2)!=EOF){
int len1=strlen(s1);
int len2=strlen(s2);
int max=0;
int start=0;
dp[0][0]=0;
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(s1[i-1]==s2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=max1 (dp[i-1][j],dp[i][j-1]);
}
if(dp[i][j]>max){
max=dp[i][j];
start=i;
}
}
}
printf("%d\n",max);
for(int i=start-max;i<=start-1;i++)printf("%c",s1[i]);
printf("\n");
}
return 0;
}
这是为啥??
登录后发布评论
因为满足代码条件的可以是:a非连续lcs == b非连续lcs ; a非连续lcs == b连续lcs ; a连续lcs == b非连续lcs ; a连续lcs == b连续lcs。而这题只需要第四种的答案,算出来的答案确是这四种的最大值,所以只能匹配33%的答案。