本文将解释如何寻找两个字符串的最长公共子序列，并计算其长度。这个问题与leetcode1143.最长公共子序列相同，读者可以在阅读完本文后尝试解决这个问题。

力扣题目链接

题目叙述：

给定两个字符串，输出它们的最长公共子序列以及其长度。

输入：

ADABEC和DBDCA

输出：

DBC
3

解释

最长公共子序列是DBC，长度为3。

动态规划思路：

• 首先，我们使用两个指针
  
  i
  
  和
  
  j
  
  来遍历字符串a和b，如下图所示：

• 然后，设想一个状态变量，也就是一个函数。对于两个相关变量的函数，我们可以用二维数组
  
  f
  
  来表示。

• 接着，
  
  f[i][j]
  
  表示什么呢？表示字符串a的前i个字符和字符串b的前j个字符的最长公共子序列的长度。

状态变量的含义

• 在这里，状态变量为
  
  f[i][j]
  
  ，表示字符串a的前i个字符和字符串b的前j个字符的最长公共子序列的长度。
• 现在要观察
  
  a[i]
  
  和
  
  b[j]
  
  是否在当前的最长公共子序列中。
• 具体情况如下图所示：

递推公式：

• 
  f[i][j]
  
  可以分为三种情况讨论：

1. 
   a[i]
   
   和
   
   b[j]
   
   都在最长公共子序列中，即
   
   a[i]==b[j]
   
2. 
   a[i]!=b[j]
   
   ，并且
   
   a[i]
   
   不在公共子序列中
3. 
   a[i]!=b[j]
   
   ，并且
   
   b[j]
   
   不在公共子序列中

• 因此，我们的递推公式可以分为两种情况：
• 
  f[i][j]=f[i-1][j-1]+1
  
  （
  
  a[i]==b[j]
  
  ）
• 
  f[i][j]=max(f[i-1][j],f[i][j-1])
  
  （
  
  a[i]!=b[j]
  
  ）
• 显而易见，我们的边界条件为：
• 
  f[0][j]=0
  
• 
  f[i][0]=0
  

//m是a字符串的长度，n是b字符串的长度
for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
        //因为我们的f数组是从下标1开始，而字符串是从0开始的下标
        if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1]+1;
        else f[i][j]=max(f[i-1][j],f[i][j-1]);
    }
}

遍历顺序

• 根据以上分析，遍历顺序为
  
  i从小到大
  
  ，
  
  j也是从小到大
  
  。

初始化

• 初始化边界为0即可

举例打印dp数组

• 如下图所示

如何找出对应的最长公共子序列的长度

• 我们使用
  
  p
  
  数组来记录每一次
  
  f[i][j]
  
  的值来源于哪一个方向：
• 1方向代表左上方
• 2方向代表左方
• 3方向代表上方
• 代码改造如下：

for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
        if(a[i-1]==b[j-1]){
            f[i][j]=f[i-1][j-1]+1;
            //左上方
            p[i][j]=1;
        }
        else if(f[i-1][j]>f[i][j-1]){
            f[i][j]=f[i][j-1];
   			//左边
            p[i][j]=2;
        }
        else{
            f[i][j]=f[i-1][j];
			//上边
            p[i][j]=3;
        }
    }
}

• 
  p[i][j]
  
  代表前驱的位置。

算法的执行过程

• 要找到最长公共子序列，只需要找到从结尾开始，往前找到
  
  p[i][j]==1
  
  的元素集合，这个集合就是最长公共子序列。
• 例子如下：

• 我们使用
  
  s数组
  
  来存储最长公共子序列
• 代码实现：

int i,j,k;
char s[200];
i=m;j=n;k=f[m][n];
while(i>0&&j>0){
    //左上方
    if(p[i][j]==1){
        s[k--]=a[i-1];
        i--;j--;
    }
    //左边
    else if(p[i][j]==2) j--;
    //上边
    else i--;
}
for(int i=1;i<=f[m][n];i++) cout<<s[i];

最终代码实现：

#include <iostream>
#include <cstring>
using namespace std;

char a[200];
char b[200];
int f[205][205];
int p[205][205];
int m, n;

void LCS() {
	int i, j;
	m = strlen(a);
	n = strlen(b);

	for (i = 1; i <= m; i++) {
		for (j = 1; j <= n; j++) {
			if (a[i - 1] == b[j - 1]) {
				f[i][j] = f[i - 1][j - 1] + 1;
				p[i][j] = 1; 
			}
			else if (f[i - 1][j] > f[i][j - 1]) {
				f[i][j] = f[i - 1][j];
				p[i][j] = 2; 
			}
			else {
				f[i][j] = f[i][j - 1];
				p[i][j] = 3; 
			}
		}
	}
	cout << f[m][n] << endl;
}
//寻找出当初的最长公共子序列。
void getLCS() {
	int i = m, j = n, k = f[m][n];
	char s[200];
	s[k] = '\0'; 
	while (i > 0 && j > 0) {
		if (p[i][j] == 1) {
			s[--k] = a[i - 1];
			i--; j--;
		}
		else if (p[i][j] == 2) {
			i--;
		}
		else {
			j--;
		}
	}

	cout << s << endl;
}

int main() {
	cin >> a >> b;
	LCS();
	getLCS();
	return 0;
}

未经允许不得转载：大白鲨游戏网 » 最长公共子序列