這題很難，我只寫(xiě)出了一個(gè)TLE的版本。
后來(lái)找了解題報(bào)告，只找到了一個(gè)，就是這位alpc43大牛的版本：
http://hi.baidu.com/alpc43/blog/item/95184e03a5fef4e209fa932d.html
這個(gè)代碼很牛逼！
它的思路是：
1）首先按照常規(guī)的方法求出最長(zhǎng)公共子序列的長(zhǎng)度
也就是用O(MN)的那個(gè)動(dòng)態(tài)規(guī)劃，結(jié)果放在二維數(shù)組dp里
dp[i][j] = { 字串a(chǎn)的1~i部分與字串b的1~j部分的最長(zhǎng)公共子序列的長(zhǎng)度 }
2）求輔助數(shù)組
last1[i][j] = { 到下標(biāo)i為止，字符j在字串a(chǎn)中最后一次出現(xiàn)的下標(biāo) }
last2[i][j] = { 到下標(biāo)i為止，字符j在字串b中最后一次出現(xiàn)的下標(biāo) }
3）枚舉最長(zhǎng)公共字串的每一個(gè)字符
從最后一個(gè)字符開(kāi)始枚舉
比如說(shuō)現(xiàn)在枚舉最后一個(gè)字符是'C'的情況。
那么 'CDCD' 與 'FUCKC' 這兩個(gè)字串。
一共有 (0, 2) (0, 4) (2, 2) (2. 4) 這四種可能。
很明顯前三個(gè)是可以舍棄的，因?yàn)榈谒膫€(gè)優(yōu)于前三個(gè)，為后續(xù)的枚舉提供了更大的空間。
last數(shù)組正好是用來(lái)做這個(gè)的。
4）排序輸出
代碼里用了stl的set。
注意，由于剛剛的枚舉過(guò)程是針對(duì)每個(gè)字符，所以是不用判重的。
這個(gè)思路非常之牛逼！
#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;
}