首页 > 编程语言 >算法设计与分析(最长公共子序列

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

时间:2024-09-24 16:21:38浏览次数:11  
标签:LCS int 字符串 算法 序列 长度 最长



目录

  • 最长公共子序列
  • 问题描述
  • 代码实现
  • 输出结果
  • 注意事项
  • 小结:


最长公共子序列

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

问题描述

给定两个字符串,LCS的目标是找出它们之间的最长子序列。对于字符串 xy,子序列是从 xy 中删除一些字符后得到的新序列,并且删除的字符的相对顺序保持不变。比如,对于字符串 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),在处理大字符串时要考虑其性能影响。


标签:LCS,int,字符串,算法,序列,长度,最长
From: https://blog.51cto.com/u_16672541/12100849

相关文章

  • 算法设计与分析(矩阵连乘问题
    目录矩阵连乘代码代码说明小结:矩阵连乘矩阵连乘问题是一个经典的动态规划问题,旨在通过确定矩阵的乘法顺序来最小化所需的乘法运算次数。在矩阵连乘中,我们有一系列矩阵(A_1,A_2,…,A_n),其维度由一个数组(p)定义,其中(p[i-1])是矩阵(A_i)的行数,而(p[i])是矩阵......
  • 日新月异 PyTorch - pytorch 基础: K-means 聚类算法(sklearn.cluster 的 KMeans 实现,
    源码https://github.com/webabcd/PytorchDemo作者webabcd日新月异PyTorch-pytorch基础:K-means聚类算法(sklearn.cluster的KMeans实现,对一个包含10个特征的数据做分类)示例如下:basic\demo07.py'''K-means聚类算法(sklearn.cluster的KMeans实现,对一个包含1......
  • 一、机器学习算法与实践_04信息论与决策树算法笔记
    1信息论基础知识介绍信息论是运用概率论与数理统计的方法,去研究信息、信息熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科,熵(Entropy)是信息论中的一个重要概念,由克劳德·香农(ClaudeShannon)提出,用于衡量信息的不确定性或系统的混乱程度在机器学习中,熵的概念......
  • 2207. 字符串中最多数目的子序列
    给你一个下标从0开始的字符串text和另一个下标从0开始且长度为2的字符串pattern,两者都只包含小写英文字母。你可以在text中任意位置插入一个字符,这个插入的字符必须是pattern[0]或者pattern[1]。注意,这个字符可以插入在text开头或者结尾的位置。请你返回插......
  • 文心一言 VS 讯飞星火 VS chatgpt (350)-- 算法导论24.1 1题
    一、在图24-4上运行Bellman-Ford算法,使用结点作为源结点。在每一遍松弛过程中,以图中相同的次序对每条边进行松弛,给出每遍松弛操作后的值和值。然后,把边的权重改为,再次运行该算法,这次使用作为源结点。如果要写代码,请用go语言。文心一言:首先,我们根据题目要求,手动通过Bellman-Ford算......
  • 文心一言 VS 讯飞星火 VS chatgpt (348)-- 算法导论23.2 7题
    七、假定图G的一棵最小生成树已经被计算出来。如果在图中加入一个新结点及其相关的新边,我们需要多少时间来对最小生成树进行更新?如果要写代码,请用go语言。文心一言:在图中加入一个新节点及其相关边后,要更新最小生成树(MST),通常意味着需要重新计算包含新节点的最小生成树,因为新节点的加......
  • 文心一言 VS 讯飞星火 VS chatgpt (347)-- 算法导论23.2 6题
    六、假定一个图中所有的边权重均匀分布在半开区间[0,1)内。Prim算法和Kruskal算法哪一个可以运行得更快?如果要写代码,请用go语言。文心一言:在比较Prim算法和Kruskal算法在特定条件下的性能时,我们需要考虑几个因素,主要是图的表示方式、边的数量、顶点的数量以及边的权重分布。由于在......
  • kl散度,K近邻估计法(K-Nearest Neighbors, KNN)是一种基本的分类与回归方法,通常用于分类
     K近邻估计法(K-NearestNeighbors,KNN)是一种基本的分类与回归方法,通常用于分类任务。在Python中,你可以使用scikit-learn库来实现KNN算法。下面是一个简单的示例,展示如何使用scikit-learn来实现KNN分类器。首先,确保你已经安装了scikit-learn库。如果没有安装,可以通过运行pipinsta......
  • 一种单目标A*算法设计与实现
    一种单目标A*算法设计与实现作者:吴屏珊最近在学习简单的单目标A*算法,其中在CSDN上阅读到的一篇博文给了我很大启发,于是在该博文的基础上,笔者记录了一点自己对于A*算法的体会和感悟。原文链接目录目录一种单目标A*算法设计与实现目录1.A*算法简单介绍1.1A*算法的基本要素1......
  • 回归预测 | Matlab实现SSA-HKELM麻雀算法优化混合核极限学习机多变量回归预测
    回归预测|Matlab实现SSA-HKELM麻雀算法优化混合核极限学习机多变量回归预测目录回归预测|Matlab实现SSA-HKELM麻雀算法优化混合核极限学习机多变量回归预测效果一览基本介绍程序设计参考资料效果一览基本介绍1.Matlab实现SSA-HKELM麻雀算法优化混合核极限学习机多变量回归预......