这题很难，我只写出了一个TLE的版本。
后来找了解题报告，只找到了一个，就是这位alpc43大牛的版本：
http://hi.baidu.com/alpc43/blog/item/95184e03a5fef4e209fa932d.html
这个代码很牛逼！
它的思路是：
1）首先按照常规的方法求出最长公共子序列的长度
也就是用O(MN)的那个动态规划，结果放在二维数组dp里
dp[i][j] = { 字串a的1~i部分与字串b的1~j部分的最长公共子序列的长度 }
2）求辅助数组
last1[i][j] = { 到下标i为止，字符j在字串a中最后一次出现的下标 }
last2[i][j] = { 到下标i为止，字符j在字串b中最后一次出现的下标 }
3）枚举最长公共字串的每一个字符
从最后一个字符开始枚举
比如说现在枚举最后一个字符是'C'的情况。
那么 'CDCD' 与 'FUCKC' 这两个字串。
一共有 (0, 2) (0, 4) (2, 2) (2. 4) 这四种可能。
很明显前三个是可以舍弃的，因为第四个优于前三个，为后续的枚举提供了更大的空间。
last数组正好是用来做这个的。
4）排序输出
代码里用了stl的set。
注意，由于刚刚的枚举过程是针对每个字符，所以是不用判重的。
这个思路非常之牛逼！
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <string>
#include <set>;
using namespace std;
const int MAXLEN=100;
char s1[MAXLEN];
char s2[MAXLEN];
int len1,len2;
int dp[MAXLEN][MAXLEN];
int last1[MAXLEN][27];
int last2[MAXLEN][27];
int longest;
char temp[MAXLEN];
set<string> SET;
void input()
{
scanf("%s %s",&s1[1],&s2[1]);
}
inline int maxab(int a,int b)
{
if(a>b) return a;
return b;
}
inline void find(int x,int y,int len)
{
if(len<=0)
{
//printf("%s\n",&temp[1]);
SET.insert(&temp[1]);
return ;
}
int i,j;
if(x>0 && y>0)
{
for(i=0;i<26;i++)
{
int t1=last1[x][i];
int t2=last2[y][i];
if(dp[t1][t2]==len)
{
temp[len]='a'+i;
find(t1-1,t2-1,len-1);
}
}
}
}
void solve()
{
int i,j,k;
len1=strlen(&s1[1]);
len2=strlen(&s2[1]);
for(i=0;i<=len1;i++)
dp[i][0]=0;
for(i=0;i<=len2;i++)
dp[0][i]=0;
for(i=1;i<=len1;i++)
for(j=1;j<=len2;j++)
{
if(s1[i]==s2[j])
dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=maxab(dp[i-1][j],dp[i][j-1]);
}
longest=dp[len1][len2];
for(j=0;j<26;j++)
for(i=0;i<=len1;i++)
last1[i][j]=0;
for(j=0;j<26;j++)
for(i=0;i<=len2;i++)
last2[i][j]=0;
for(i=1;i<=len1;i++)
{
for(j=0;j<26;j++)
{
if(s1[i]=='a'+j)
last1[i][j]=i;
else last1[i][j]=last1[i-1][j];
}
}
for(i=1;i<=len2;i++)
{
for(j=0;j<26;j++)
{
if(s2[i]=='a'+j)
last2[i][j]=i;
else last2[i][j]=last2[i-1][j];
}
}
temp[longest+1]='\0';
find(len1,len2,longest);
set<string>::iterator it;
for(it=SET.begin();it!=SET.end();it++)
{
printf("%s\n",(*it).c_str());
}
}
int main()
{
freopen("e:\\in.txt", "r", stdin);
input();
solve();
return 0;
}