这题很难，我只写出了一个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。
注意，由于刚刚的枚举过程是针对每个字符，所以是不用判重的。

这个思路非常之牛逼！

• 没必要这么复杂吧……我直接归并排序爆搞，没有刻意常数优化，pascal都0ms…… (645) xuhaoran510 2011-06-20 20:20:17
  • Re:没必要这么复杂吧……我直接归并排序爆搞，没有刻意常数优化，pascal都0ms…… (3) peargobble 2011-06-20 20:44:59
• 也可以都反过来，弄2个first数组，dp求最长LCS长度时从后往前递推（用于dfs时减枝），求所有LCS时顺着走，每位从a试到z，这样，就不用排序了…… (1424) xieofyu 2012-09-03 15:37:29