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

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

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

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

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

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。其他情况下，由定理可建立递归关系如下：

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

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

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

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

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

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

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

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

模板代码：

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(longest common subsequence)（最长公共子序列）算法（模板）

问题描述

LCS问题的解决思路

动态规划算法解LCS问题

模板代码：

相关推荐