LCS, LIS, 线性空间LCS( hirschberg算法)

首先是LCS（longest common substring最长公共子序列），这是动态规划的典型例题，各种算法书里都会讲到的一个问题.维基上的介绍：

 

LIS（longest increasing substring）也是一个动态规划问题，有O(n²)以及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算法可以使用线性空间获得最长子序列的长度