讨论 - 谁给我说一下这道题的思路...我不会啊

原始鸭 2008-08-23 02:31:00

点我顶贴收藏删除

我看着上面写着动态规划..大家又说查找..快排,我糊涂了啊

#1 世纪末的魔术师@2008-08-11 20:45:00

回复删除

呃。。这题的思路是找到两个数字串的最大公共子串的长度，因为只要找到最大的子串，剩下来的那些可以自由变到目标位置。

而要找到最大公共子串，我们可以把问题转化为求最长不下降子序列。

怎样求最长不下降子序列呢？我们需要生成第三个数组C，当A[j]=B[i]时，C[i]=j；这个数组什么意义呢？你自己想想吧，然后对这个数组求最长不下降子序列，这个最长不下降子序列的长度就是最大公共子串的长度。

N减去它就是答案。

生成C数组的复杂度为O(n),求Lis是O(nlogn)。这样就是思路了。

#2 wish@2008-08-11 21:54:00

回复删除

LZ 如果看不懂题解的话，LS 的方法估计也不明白

你可以先研究下 LIS 的 O(nlgn) 算法

#3 xiaokeke@2008-08-23 02:15:00

回复删除

LIS的优化我明白

但是为什么能得出c数组呢？为什么要lis呢？

望牛解答……

#4 xiaokeke@2008-08-23 02:31:00

回复删除

我懂了……

太经典了Orz