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

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

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

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

N减去它就是答案。

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

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

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

LIS的优化我明白

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

望牛解答……

我懂了……

太经典了Orz