经典问题 : 字符串的最大公共子序列

估计很多研究过的人都知道，不过也有很多不清楚的。

求字符串的最大公共子序列(非子串)。
比如两个字符串：abcdefg 和 acbedff 的最大公共子序列是：abef

求出子序列，非子序列长度

LCS是有n^2的DP方法的，好像没听说有更好的办法

状态公式是
dp[i][j] = max{dp[i][j-1], dp[i-1][j], dp[i-1][j-1]+1 if str1[i] == str2[j]}
时间复杂度当然是O(n^2),

如果只是求长度，空间复杂度为O(n)就可以了。
如果要求出具体是什么序列，需要用DP[n][m]，二维数组记录。

从DP[n-1][m-1]开始，如果DP[i][j] == DP[i-1][j-1]+1,则记录下str1[i] (或str2[j])，如果DP[i][j] == DP[i-1][j-1], 则可以选择任意一条路径。

DP[m][n]，也可以求出一些特定要求的子序列(如在str1中距离最短的最大子序列)

子序列应该如何定义呢？这里似乎除了abef以外，acef, abdf, acdf都可以算子序列吧？

子序列应该如何定义呢？这里似乎除了abef以外，acef, abdf, acdf都可以算子序列吧？
currahee 发表于 2011-5-31 22:03

    都可以算，顺序相同就可以了