Description
Input
Output
Sample Input
die einkommen der landwirte sind fuer die abgeordneten ein buch mit sieben siegeln um dem abzuhelfen muessen dringend alle subventionsgesetze verbessert werden # die steuern auf vermoegen und einkommen sollten nach meinung der abgeordneten nachdruecklich erhoben werden dazu muessen die kontrollbefugnisse der finanzbehoerden dringend verbessert werden #
Sample Output
die einkommen der abgeordneten muessen dringend verbessert werden
单词的LCS，要递归输出=-=，我脑袋大笨，竟在比赛时想着模拟
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<limits.h>
using namespace std;
char s1[110][110],s2[110][110];
char s[110][110];
int mark[110][110],dp[110][110];
int len1,len2,num;
void LCS()
{
memset(dp,0,sizeof(dp));
memset(mark,0,sizeof(mark));
for(int i=0;i<=len1;i++)
mark[i][0]=1;
for(int i=0;i<=len2;i++)
mark[0][i]=-1;
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(!strcmp(s1[i-1],s2[j-1]))
{
dp[i][j]=dp[i-1][j-1]+1;
mark[i][j]=0;//mark为0代表s1[i-1]=s2[j-1]便于递归输出
}
else if(dp[i-1][j]>=dp[i][j-1])
{
dp[i][j]=dp[i-1][j];
mark[i][j]=1;//同理
}
else
{
dp[i][j]=dp[i][j-1];
mark[i][j]=-1;
}
}
}
}
void print(int i,int j)
{
if(!i&&!j)
return ;
if(mark[i][j]==0)
{
print(i-1,j-1);
strcpy(s[num++],s1[i-1]);
}
else if(mark[i][j]==1)
print(i-1,j);
else
print(i,j-1);
}
int main()
{
while(~scanf("%s",s1[0]))
{
len1=1;
while(strcmp(s1[len1-1],"#"))
scanf("%s",s1[len1++]);
scanf("%s",s2[0]);
len2=1;
while(strcmp(s2[len2-1],"#"))
scanf("%s",s2[len2++]);
len1--;
len2--;
num=0;
LCS();
print(len1,len2);
printf("%s",s[0]);
for(int i=1;i<num;i++)
printf(" %s",s[i]);
printf("\n");
}
return 0;
}
周赛 POJ 2250 Compromise,布布扣,bubuko.com
原文：http://blog.csdn.net/u013582254/article/details/38395443