LCS(longest common subsequence)（最长公共子序列）算法（模板）

谁践踏了优雅 2022-05-11 14:54 178阅读 0赞

看了几分写的相当好的博客：

介绍：[程序员编程艺术第十一章：最长公共子序列(LCS)问题][LCS]

表格展示：[LCS算法（最长公共子序列问题）][LCS 1]

代码：[ 算法导论-动态规划(最长公共子序列问题LCS)-C++实现][_-_LCS_-C]

[C++实现——LCS-最大公共子串长度][C_LCS-]

下面内容来转载自上面文章

### 问题描述 ###

什么是最长公共子序列呢?好比一个数列 S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。

举个例子，如：有两条随机序列，如 1 3 4 5 5 ，and 2 4 5 5 7 6，则它们的最长公共子序列便是：4 5 5。

注意最长公共子串（Longest CommonSubstring）和最长公共子序列（LongestCommon Subsequence, LCS）的区别：子串（Substring）是串的一个连续的部分，子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串acdfg同akdfc的最长公共子串为df，而他们的最长公共子序列是adf。LCS可以使用动态规划法解决。下文具体描述。

## LCS问题的解决思路 ##

**穷举法**

解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。X和Y的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列\{1, 2, …, m\}的一个子序列，因此，X共有2m个不同子序列（Y亦如此，如为2^n），从而穷举搜索法需要指数时间（2^m \* 2^n）。

**动态规划算法**

事实上，最长公共子序列问题也有最优子结构性质。

记：

> Xi=﹤x1，⋯，xi﹥即X序列的前i个字符 (1≤i≤m)（前缀）
> 
> Yj=﹤y1，⋯，yj﹥即Y序列的前j个字符 (1≤j≤n)（前缀）

假定Z=﹤z1，⋯，zk﹥∈LCS(X , Y)。

若**xm=yn**（最后一个字符相同），则不难用反证法证明：该字符必是X与Y的任一最长公共子序列Z（设长度为k）的最后一个字符，即有zk = xm = yn 且显然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的前缀Zk-1是Xm-1与Yn-1的最长公共子序列。此时，问题化归成求Xm-1与Yn-1的LCS（LCS(X , Y)的长度等于LCS(Xm-1 , Yn-1)的长度加1）。

若**xm≠yn，**则亦不难用反证法证明：要么Z∈LCS(Xm-1, Y)，要么Z∈LCS(X , Yn-1)。由于zk≠xm与zk≠yn其中至少有一个必成立，若zk≠xm则有Z∈LCS(Xm-1 , Y)，类似的，若zk≠yn 则有Z∈LCS(X , Yn-1)。此时，问题化归成求Xm-1与Y的LCS及X与Yn-1的LCS。LCS(X , Y)的长度为：max\{LCS(Xm-1 , Y)的长度, LCS(X , Yn-1)的长度\}。

由于上述当xm≠yn的情况中，求LCS(Xm-1 , Y)的长度与LCS(X , Yn-1)的长度，这两个问题不是相互独立的：两者都需要求LCS(Xm-1，Yn-1)的长度。另外两个序列的LCS中包含了两个序列的前缀的LCS，故问题具有最优子结构性质考虑用动态规划法。

也就是说，解决这个LCS问题，你要求三个方面的东西：1、LCS（Xm-1，Yn-1）+1；2、LCS（Xm-1，Y），LCS（X，Yn-1）；3、max\{LCS（Xm-1，Y），LCS（X，Yn-1）\}。

行文至此，其实对这个LCS的动态规划解法已叙述殆尽，不过，为了成书的某种必要性，下面，我试着再多加详细阐述这个问题。

##    动态规划算法解LCS问题 ##

1、最长公共子序列的结构

最长公共子序列的结构有如下表示：

设序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一个最长公共子序列Z=<z1, z2, …, zk>，则：

若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；  
    若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；  
    若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。

其中Xm-1=<x1, x2, …, xm-1>，Yn-1=<y1, y2, …, yn-1>，Zk-1=<z1, z2, …, zk-1>。

2.子问题的递归结构

由最长公共子序列问题的最优子结构性质可知，要找出X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。

由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。

与矩阵连乘积最优计算次序问题类似，我们来建立子问题的最优值的递归关系。用c\[i,j\]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=<x1, x2, …, xi>，Yj=<y1, y2, …, yj>。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c\[i,j\]=0。其他情况下，由定理可建立递归关系如下：

> ![0_1313577392SuoV.gif][]

上面得出状态转换公式，也是下面填表和程序实现的依据。

在填充单元格时，需要考虑以下条件：

*  它左侧的单元格
 *  它上面的单元格
 *  它左上侧的单元格

![70][]

这种方法的思路是：将从上向下、从左到右填充表格。（类似于非常经典的动态规划——背包问题的填表）

![70 1][]

![70 2][]

![70 3][]

请注意，我在图中还添加了箭头，指向当前单元格值的来源。

![70 4][]

## **模板代码：** ##

LCS长度

> void lcsLength(string x,string y, vector< vector<int>> &c, vector< vector<char>> &b)  
> \{  
>     int m = x.size();  
>     int n = y.size();  
>     c.resize(m+1);  
>     b.resize(m+1);  
>     for(int i = 0; i < c.size(); ++i)  
>         c\[i\].resize(n+1);  
>     for(int i = 0; i < b.size(); ++i)  
>         b\[i\].resize(n+1);
> 
>     for(int i = 1; i <= m; ++i)\{  
>         for(int j = 1; j <= n; ++j)\{  
>             if(x\[i-1\] == y\[j-1\])\{  
>                 c\[i\]\[j\] = c\[i-1\]\[j-1\]+1;  
>                 b\[i\]\[j\] = 'c';  
>             \}else if(c\[i-1\]\[j\] >= c\[i\]\[j-1\])\{  
>                 c\[i\]\[j\] = c\[i-1\]\[j\];  
>                 b\[i\]\[j\] ='u';  
>             \}else\{  
>                 c\[i\]\[j\] = c\[i\]\[j-1\];  
>                 b\[i\]\[j\] = 'l';  
>             \}  
>         \}  
>     \}  
> \}

LCS的递归打印：

> void print\_lcs(vector< vector<char>> &b,string x, int i, int j)  
> \{  
>     if(i == 0 || j == 0)  
>         return;  
>     if(b\[i\]\[j\] == 'c')\{  
>         print\_lcs(b,x,i-1,j-1);  
>         cout << x\[i-1\];  
>     \}else if(b\[i\]\[j\] == 'u')  
>         print\_lcs(b,x,i-1,j);  
>     else  
>         print\_lcs(b,x,i,j-1);  
> \}

LCS的非递归打印（也可以用栈进行实现）：

> char c\[1010\];  
>         while(m > 0 && n > 0)//从终点按标记的方向反方向往回走  
>         \{  
>             if(flag\[m\]\[n\] == 1)\{ //这个方向来的元素包含在最长公共子序列中  
>                 c\[k++\] = a\[m - 1\];  
>                 m--; n--;  
>             \}  
>             else if(flag\[m\]\[n\] == 2)  
>                 m--;  
>             else if(flag\[m\]\[n\] == 3)  
>                 n--;  
>         \}  
>         for(i = k-1;i >= 0;i--)  
>             printf("%c",c\[i\]);  
>         printf("\\n");

LCS代码模板合成：

//LCS(longest common subsequence) 最长公共子序列算法
    //dacao
    //2018/10/21
    
    #include<iostream>
    #include<vector>
    #include<stack>
    using namespace std;
    
    void LCS_length(string x,string y,vector<vector<int> >&dp,vector<vector<char> > &flag)
    {
    	int m=x.length();
    	int n=y.length();
    	dp.resize(m+1);
    	flag.resize(m+1);
    	int i,j;
    	for(i=0;i<dp.size();i++)
    		dp[i].resize(n+1);
    	for(i=0;i<flag.size();i++)
    		flag[i].resize(n+1);
    		
    	for(i=1;i<=m;i++)
    	{
    		for(j=1;j<=n;j++)
    		{
    			if(x[i-1]==y[j-1])
    			{
    				dp[i][j]=dp[i-1][j-1]+1;
    				flag[i][j]='c';
    			}
    			else if(dp[i-1][j] >= dp[i][j-1])
    			{
    				dp[i][j]=dp[i-1][j];
    				flag[i][j]='u';//来源于上面 
    			}
    			else
    			{
    				dp[i][j]=dp[i][j-1];
    				flag[i][j]='l';//来源于左边 
    			}
    		}
    	}
    }
    
    void dp_print_lcs(vector<vector<char> > &flag,string &x,int i,int j)
    {
    	if(i==0||j==0)
    		return;
    	if(flag[i][j]=='c')
    	{
    		dp_print_lcs(flag,x,i-1,j-1);
    		cout<<x[i-1];
    	}
    	else if(flag[i][j]=='u')
    		dp_print_lcs(flag,x,i-1,j);
    	else
    		dp_print_lcs(flag,x,i,j-1);
    } 
    
    void stack_print_lcs(vector<vector<char> > &flag,string &x,int i,int j)
    {
    	stack<char> ans;
    	while(i>0&&j>0)//入栈 
    	{
    		if(flag[i][j]=='c')
    		{
    			ans.push(x[i-1]);
    			i--;
    			j--;
    		}
    		else if(flag[i][j]=='u')
    			i--;
    		else
    			j--;
    	}
    	
    	while(!ans.empty())
    	{
    		cout<<ans.top();
    		ans.pop();
    	} 
    }
    
    int main()
    {
        string x = "ABCBDAB";
        string y = "BDCABA";
        vector< vector<int> > dp;
        vector< vector<char> > flag;
    
        LCS_length(x,y,dp,flag);
        //dp_print_lcs(flag,x,x.size(),y.size());
        stack_print_lcs(flag,x,x.size(),y.size());
        
        return 0;
    }

[LCS]: https://blog.csdn.net/v_july_v/article/details/6695482
[LCS 1]: https://blog.csdn.net/exchan/article/details/52244015
[_-_LCS_-C]: https://www.cnblogs.com/zlm-jessie/p/5664562.html
[C_LCS-]: https://blog.csdn.net/langmanqishizaijia/article/details/51096951
[0_1313577392SuoV.gif]: /images/20220505/f0c13b0f1de6421199bd8a9c4ef54e78.png
[70]: /images/20220505/3b4017dd47ba4a3c9c25031bb57a7c60.png
[70 1]: /images/20220505/fad9cdad59c7487aa8e55e070ec01afe.png
[70 2]: /images/20220505/b4694def814f413cb46cf634142dd1a9.png
[70 3]: /images/20220505/aba5f6231e27471782280a3031d752a6.png
[70 4]: /images/20220505/66bd34f48a6a457ab8c5728036743be4.png