#include <iostream>
#include <string>
using namespace std;
string op[102];
int f[102][102],opt[102][102];
int len;
string a[102],b[102];
void search(int i,int j)
{
	if(i<=0||j<=0)
		return;
	else if(opt[i][j]==0)
		{
			op[len--]=a[i];
			search(i-1,j-1);
		}
	else if(opt[i][j]==1)
		search(i-1,j);
	else
		search(i,j-1);			
}
int  main()
{

int i=1,j=1;
int lena,lenb;
	cin>>a[1];
while(a[i]!="#")
	{
		i++;
		cin>>a[i];
	}
	lena=i-1;
	cin>>b[1];
while(b[i]!="#")
	{
		i++;
		cin>>b[i];
	}
	lenb=i-1;

 for(i=0;i<=lena;i++)
 	f[i][0]=0;
 for(j=0;j<=lenb;j++)
 	f[0][j]=0;
 	
 for(i=1;i<=lena;i++)
 for(j=1;j<=lenb;j++)	
	 {
	 	if(a[i]==b[j])
			{ f[i][j]= f[i-1][j-1]+1;opt[i][j]=0;}
		else if(f[i-1][j]>=f[i][j-1])
			{f[i][j]=f[i-1][j];opt[i][j]=1;}
		else
			{f[i][j]=f[i][j-1];opt[i][j]=-1;}
	 }
	 len=f[lena][lenb]; 
	 search(lena,lenb);		
	for(i=1;i<=f[lena][lenb];i++)
	 cout<<op[i]<<" ";
	 cout<<endl;
 return 1;
}

• Re:哪位大哥看看错在哪里啊... (48) snowfall 2008-09-23 21:07:26