#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;

char s[85],t[85],st[85];
short dp[85][85],f[85][30],g[85][30],k,lens,lent,val;

struct point
{
	char str[85];
};
point p[1005];

bool cmp(point p1,point p2)
{
	return strcmp(p1.str,p2.str) < 0;
}
int max(int a,int b)
{
	if(a > b) return a;
	return b;
}

void dfs(int lens,int lent,int len)
{
	if(len == 0)
	{
		k ++;
		st[val] = '\0';
		strcpy(p[k].str,st);
		return;
	}
	for(int i = 0;i < 26;i ++)
	{
		if(f[lens][i] && g[lent][i] && dp[f[lens][i]][g[lent][i]] == len)
		{
			st[val-len] = 'a' + i;
			dfs(f[lens][i]-1,g[lent][i]-1,len-1);
		}
	}
}
int main()
{
	int i,j;
	scanf("%s",s+1);
	scanf("%s",t+1);
	lens = strlen(s+1);
	lent = strlen(t+1);
	memset(dp,0,sizeof(dp));
	for(i = 1;i <= lens;i ++)
		for(j = 1;j <= lent;j ++)
		{
			if(s[i] == t[j])
				dp[i][j] = dp[i-1][j-1] + 1;
			else
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
		}
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	for(i = 1;i <= lens;i ++)
		for(j = 0;j < 26;j ++)
		{
			if(s[i] - 'a' == j)
				f[i][j] = i;
			else
				f[i][j] = f[i-1][j];
		}
	
	for(i = 1;i <= lent;i ++)
		for(j = 0;j < 26;j ++)
		{
			if(t[i] - 'a' == j)
				g[i][j] = i;
			else
				g[i][j] = g[i-1][j];
		}
	k = 0;
	val = dp[lens][lent];
    dfs(lens,lent,val);
	char temp;
	for(i = 1;i <= k;i ++)
	{
		for(j = 0;j <= val/2;j ++)
		{
            temp = p[i].str[j];
			p[i].str[j] = p[i].str[val-j-1];
			p[i].str[val-j-1] = temp;
		}
	}
	sort(p + 1,p + k + 1,cmp);
	for(i = 1;i <= k;i ++)
	{
		for(j = 0;j < val;j ++)
			printf("%c",p[i].str[j]);
		printf("\n");
	}
	return 0;
}

• 这些数据都通过了！！！ (1667) xiaoxiaohong 2010-03-19 18:56:01