#1 世纪末的魔术师@2008-08-11 20:45:00
4384
回复
删除
呃。。这题的思路是找到两个数字串的最大公共子串的长度,因为只要找到最大的子串,剩下来的那些可以自由变到目标位置。
而要找到最大公共子串,我们可以把问题转化为求最长不下降子序列。
怎样求最长不下降子序列呢?我们需要生成第三个数组C,当A[j]=B[i]时,C[i]=j;这个数组什么意义呢?你自己想想吧,然后对这个数组求最长不下降子序列,这个最长不下降子序列的长度就是最大公共子串的长度。
N减去它就是答案。
生成C数组的复杂度为O(n),求Lis是O(nlogn)。这样就是思路了。