#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#define N 1000
#define M 10010
using namespace std;
struct ju{
	int key,num;
}matrix[N][N];//num用来记录最长值，key用来标记

struct end{
	char s[N];
	/*bool operator<(const char a[N])const{
		return (strcmp(a,Node.s)>0? a:Node.s);
	}*/
}Node;
struct end ans[M];

bool cmp(struct end a,struct end b)//排序准则
{
	return strcmp(a.s,b.s)<0;
}
char str1[N],str2[N];
int num=0;

void cpy(char a[N],char b[N])
{
	int i,j;
	for(i=0;i<=b[0];i++)
		a[i]=b[i];
}
void strcpy(char a[N],char b[N])
{
	int i;
	for(i=b[0];i>0;i--)
		a[b[0]-i]=b[i];
	a[b[0]]='\0';
}
void Printf(int n,int m,char a[N])//回溯求最短公共子序列
{
	char b[N];
	int i,j;
	if(n==0||m==0)
	{
		strcpy(ans[num++].s,a);
		return;
	}
	cpy(b,a);
	if(matrix[n][m].key==2)
	{
		b[++b[0]]=str1[n-1];		
		Printf(n-1,m-1,b);
		return;
	}
	switch(matrix[n][m].key)
	{
	case 0:Printf(n-1,m,b);Printf(n,m-1,b);break;
	case 1:Printf(n,m-1,b);break;
	case -1:Printf(n-1,m,b);break;
	}
}

int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int i,j,k;
	for(i=0;i<=N;i++)
		matrix[0][i].num=matrix[i][0].num=0;

	scanf("%s%s",str1,str2);
	int n=strlen(str1),m=strlen(str2);
	for(i=1;i<=n;i++)//求最长公共子序列并标记
	{
		for(j=1;j<=m;j++){
			if(str1[i-1]==str2[j-1]){
				matrix[i][j].key=2;
				matrix[i][j].num=matrix[i-1][j-1].num+1;
			}
			else{
				if(matrix[i][j-1].num==matrix[i-1][j].num){
					matrix[i][j].num=matrix[i][j-1].num;
					matrix[i][j].key=0;
				}
				else{
					if(matrix[i-1][j].num>matrix[i][j-1].num){
						matrix[i][j].num=matrix[i-1][j].num;
						matrix[i][j].key=-1;
					}
					else{
						matrix[i][j].num=matrix[i][j-1].num;								;
						matrix[i][j].key=1;
					}
				}
			}
		}
	}
	num=0;
	char b[N];
	b[0]=0;
	Printf(n,m,b);
	sort(ans,ans+num,cmp);
	printf("%s\n",ans[0].s);
	i=1;
	while(i<num)//去重输出
	{
		if(strcmp(ans[i].s,ans[i-1].s))
		printf("%s\n",ans[i].s);
		i++;
	}	
}

• Re:不知道为什么一直RE！！ (37) nyistjiang 2012-04-17 20:59:21
  • 出题的给个测试数据吧！！！！都做一天了！！ (0) nyistjiang 2012-04-17 21:00:15
• Re:不知道为什么一直RE！！ (22) 201150080226 2012-07-17 20:08:50
  • Re:不知道为什么一直RE！！ (18) wukewen 2014-10-09 21:12:46