算法设计与分析（最长公共子序列

目录

• 最长公共子序列

• 问题描述
• 代码实现
• 输出结果
• 注意事项

• 小结：

最长公共子序列

最长公共子序列（Longest Common Subsequence, LCS）问题是计算给定两个序列的最长子序列的长度，这个子序列不要求连续，但需要保持相同的相对顺序。LCS广泛应用于文本比较、DNA序列分析等领域。

问题描述

给定两个字符串，LCS的目标是找出它们之间的最长子序列。对于字符串 x 和 y，子序列是从 x 或 y 中删除一些字符后得到的新序列，并且删除的字符的相对顺序保持不变。比如，对于字符串 x = "abcde" 和 y = "ace"，它们的LCS是 "ace"，长度为3。

该问题可以使用动态规划的方法高效地解决。我们通过构建一个二维数组来存储子问题的解，从而避免重复计算。

代码实现

#include <iostream> 

#define M 5
#define N 3

using namespace std;

// 递推求最优值
void LCSLength(int m, int n, char *x, char *y, int c[][N+1], int b[][N+1]){
	/*
	m：长度	x：字符串
	n：长度	y：字符串 
	c：最优值
	b：最优解 
	*/
	// 初始化
	for (int i=1; i<= m; i++) c[i][0] = 0;
	for (int j=1; j<= n; j++) c[0][j] = 0;
	
	for (int i=1; i<=m; i++){
		for (int j=1; j<=n; j++){
			if (x[i] == y[j]){
				c[i][j] = c[i-1][j-1] + 1;
				b[i][j] = 1;
			}
			else if(c[i-1][j] >= c[i][j-1]){
				c[i][j] = c[i-1][j];
				b[i][j] = 2; 
			}
			else {
				c[i][j] = c[i][j-1];
				b[i][j] = 3; 
			}
		}
	}
}

// 递归构建最优解
void LCS(int i, int j, char *x, int b[][N+1]) {
	// 终止条件
	if (i == 0 || j == 0) return;
	// 递归 
	if (b[i][j] == 1){
		LCS(i-1, j-1, x, b);
		cout << x[i];
	} 
	else if (b[i][j] == 2){
		LCS(i-1, j, x, b);
	}
	else{
		LCS(i, j-1, x, b);
	}
}

int main() {
	char x[M+1] = {'0', 'a', 'b', 'c', 'd', 'e'}; 
	char y[N+1] = {'0', 'a', 'c', 'e'}; 
	int c[M+1][N+1], b[M+1][N+1]; 
	
	// 最优值
	LCSLength(M, N, x, y, c, b); 
	
	// 最优解
	LCS(M, N, x, b);
}

输出结果

运行上述代码后，将输出两个字符串的最长公共子序列。对于 x = “abcde” 和 y = “ace”，输出将为：

注意事项

在实现LCS算法时，要注意数组索引的正确性，尤其是在处理字符数组时，确保访问正确的字符。

对于输入字符串的长度，可以根据实际需求调整常量 M 和 N，以适应不同长度的字符串。

动态规划算法的时间复杂度为O(mn)，空间复杂度也为O(mn)，在处理大字符串时要考虑其性能影响。