#include<stdio.h>
#include<string.h>

int max(int a,int b)
{
	return (a>b ? a:b);
}
int d[110][110];
char s1[110][40],s2[110][40];
int p[110][110], pos[100];
int count;
void print(int i,int j)//
{
	if (i == 0 && j == 0) return ;
	if (p[i][j] == 1)
	{
		print(i-1,j-1);
		pos[count++]=i;
	}
	else if (2 == p[i][j])
		print(i,j - 1);
	else if (3 == p[i][j])
		print(i-1,j);
}
int main()
{
	char s[40];
	while(scanf("%s",s)!=EOF)
	{
		
		strcpy(s1[1],s);
		int c1=1,c2=0;
	    while(true)
	    {
		 scanf("%s",s1[++c1]);
		 if(s1[c1][0]=='#') break;
	    }
		getchar();
		while(true)
		{
		  scanf("%s",s2[++c2]);
		  if(s2[c2][0]=='#') break;
		}
		c1--;
		c2--;
		
		for(int i=0;i<=c1;i++) d[i][0]=0;
		for(int i=1;i<=c2;i++) d[0][i]=0;

		for(int i=1;i<=c1;i++)
			for(int j=1;j<=c2;j++)
			{
				if(strcmp(s1[i],s2[j])==0)
				{
					d[i][j]=d[i-1][j-1]+1;
					p[i][j]=1;                              ////////
				}
				else
				{
					d[i][j] = max(d[i-1][j],d[i][j-1]);
					if(d[i-1][j]<d[i][j-1]) p[i][j]=2;     ////////
					else p[i][j]=3;                        ////////
				}
			}
		memset(pos,0,sizeof(pos));
		count=0;
		print(c1,c2);
		for(int i=0;i<count-1;i++) printf("%s ",s1[pos[i]]);
		printf("%s\n",s1[pos[count-1]]);
	}
	return 0;
}

• 不知道怎么回事儿在HOJ就是A不掉，，在POJac了在HOJ是WA。。。 (1858) javawin 2011-02-24 23:38:30