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

• Re:没必要这么复杂吧……我直接归并排序爆搞，没有刻意常数优化，pascal都0ms…… (3) peargobble 2011-06-20 20:44:59