首先是LCS(longest common substring最长公共子序列),这是动态规划的典型例题,各种算法书里都会讲到的一个问题.维基上的介绍:
LIS(longest increasing substring)也是一个动态规划问题,有O(n2)以及O(nlogn)两种解法,我用了比较简单的算法。具体的递推公式是:len(i) = max{str[i] > str[j]? len[i]+1 : 1} 0=< j < i; 然后我们从len的数组中找到最长子串,注意不是说最后一个len一定是最长的。然后输出。
线性空间LCS,这是使用线性的空间来解LCS问题,主要为了解决长字符串而由hirschberg发明的。可以看维基上的介绍:,当然也可以找他的论文看看,名字叫:A Linear Space Algorithm for Computing Maximal Common Subsequences 。这个解法使用到了动态规划以及分治算法,在时间复杂度上面有所增加,但是减少了空间复杂度。它首先把a数组一分为二,然后考虑所有的b数组二分的方法,找到一个subsequence最长的方法,然后将两个数组一分为二,分别再次计算。这个算法之所以可以成功,还有一个原因就是下面代码中的LCS_B算法可以使用线性空间获得最长子序列的长度
阅读(4395) | 评论(0) | 转发(0) |