序列的最长公共子序列算法
最长公共子序列（Longest Common Subsequence，LCS）是求解两个序列的公共最长子序列，被广泛应用于压缩、寻找序列间的相似性、验证递归算法等方面。该算法采用动态规划的方式求解，时间复杂度为O(nm)，其中n和m分别为两个序列的长度。
1、定义
序列A和B的最长公共子序列是指一个序列C，它是在A和B的所有子序列中最长的那个。例如，对于序列A=“AGCAT”和B=“GAC”, “GA”是它们的最长公共子序列。
2、求解
采用动态规划的方式求解，首先需要定义状态和状态转移方程。
状态：令L(i, j)表示序列A前i个字符和序列B前j个字符的最长公共子序列的长度。
状态转移方程：当A[i]=B[j]时，则L(i, j) = L(i -1, j -1) + 1；当A[i]不等于B[j]时，则L(i, j) = max{L(i - 1, j), L(i, j - 1)}。
其中，max{a, b}表示a和b的最大值。
代码实现：
int LCS(char* A,char *B,int lenA,int lenB){
int C[lenA+1][lenB+1];
for(int i=0;i<=lenA;i++){
for(int j=0;j<=lenB;j++){
if(i==0||j==0)
C[i][j]=0;
else if(A[i-1]==B[j-1])
C[i][j]=C[i-1][j-1]+1;
else
C[i][j]=max(C[i-1][j],C[i][j-1]);
}
}
return C[lenA][lenB];
}
3、优化
上述实现方法的时间复杂度为O(nm)，能满足绝大部分应用的需求。但是，在某些条件下，可进行优化。
3.1 空间优化
上述实现方法会开辟一个长度为(n+1)×(m+1)的二维数组，空间复杂度为O(nm)。但是，实际上在计算C[i][j]时，只用到了C[i-1][j]，C[i][j-1]和C[i-1][j-1]这三个元素。因此，可以用一个一维数组c[j]表示A[0~i-1]与B[0~j-1]的LCS。每次计算c[j]的值时，只需要使用之前计算的c[j-1]和C[j]的值即可，将二维数组优化为一维数组，空间复杂度为O(min(lenA,lenB))。
代码实现：
int LCS(char* A,char *B,int lenA,int lenB){
int C[min(lenA,lenB)+1];
memset(C,0,sizeof(C));
for(int i=1;i<=lenA;i++){
int last=0;
for(int j=1;j<=lenB;j++){
int tmp=C[j];
if(A[i-1]==B[j-1])
C[j]=last+1;
else
C[j]=max(C[j],C[j-1]);
last=tmp;
}
}
return C[lenB];
}
3.2 反向输出LCS
上述实现方法仅仅返回了最长公共子序列的长度，如果要输出该序列，需要进行进一步处理。可以采用反向输出法，从LCS最右端开始向左遍历，每当L(i,j)=max{L(i-1,j),L(i,j-1)}时，将A[i-1]和B[j-1]中较大的那个加入到结果序列中。
代码实现：
void PrintLCS(char* A,char* B,int lenA,int lenB,int** c){
if(lenA==0||lenB==0)
return;
if(A[lenA-1]==B[lenB-1]){
PrintLCS(A,B,lenA-1,lenB-1,c);
printf("%c",A[lenA-1]);
}else{
if(c[lenA-1][lenB]>c[lenA][lenB-1])
PrintLCS(A,B,lenA-1,lenB,c);
else
PrintLCS(A,B,lenA,lenB-1,c);
}
}
4、应用
最长公共子序列算法被广泛应用于：
压缩：在压缩数据时，如果两个字符串之间相似度高，就可以考虑使用它们的LCS作为公共部分，只保留前缀和后缀。
寻找序列间的相似性：在序列比对的过程中，可以通过求解两个序列的LCS，来寻找它们之间的相似性。
验证递归算法：一些递归算法实现时需要多次计算相同的子问题，LCS算法可以用来确定这样的重复计算是否可以优化。
5、总结
最长公共子序列算法是一种经典的算法，被广泛应用于压缩、序列比对和递归算法优化等领域。该算法采用动态规划的方式求解，时间复杂度为O(nm)，可以进行一些优化，包括空间优化和反向输出LCS。
《序列的最长公共子序列算法》相关文档：
序列的最长公共子序列算法06-23
最长公共上升子序列(LCIS)的平方算法06-23
最长公共子序列长度06-23
最长公共子序列代码06-23
最长递增子序列06-23
最长公共子序列全部解06-23
最长公共子序列 二分优化06-23
最长公共子序列长度10-28
最长公共子序列代码11-23
序列的最长公共子序列算法12-17
