当前位置: 首页 > news >正文

LCS最长公共子序列C++实现

算法思路:动态规划

 

版本1:只输出公共长度

 

#include <iostream>
#include <string>
using namespace std;int c[1000][1000]; //c[i][j]用来存储 Xi到Yj的最长公共子序列长度 void MaxLength(int m, int n, string x, string y) { //m,n分别表示字符串x和字符串y的长度 int i, j; for (i = 0; i <= m; i++) // 当j为0的时候,空序列是Xi到Yj的最长公共子序列,所以赋值0,注意这里i从0开始c[i][0] = 0;for (i = 0; i <= n; i++) // 当x为0的时候,空序列是Xi到Yj的最长公共子序列,所以赋值0,注意这里i从0开始c[0][i] = 0;for (i = 1; i <= m; i++) {  for (j = 1; j <= n; j++) { if (x[i - 1] == y[j - 1]) {  // 索引要减1,因为字符串从0开始c[i][j] = c[i - 1][j - 1] + 1;} else {c[i][j] = max(c[i - 1][j], c[i][j - 1]); }}} 
}int main() {string x, y;cin >> x >> y;int m = x.length();  // 得到字符串x的长度 int n = y.length();   // 得到字符串y的长度 MaxLength(m, n, x, y); int precent = 0; if (c[m][n]!= 0) {precent = (c[m][n] * 100) / min(m, n);}cout << "公共长度:" << c[m][n] << endl; return 0;
}

版本2:输出长度,比较相似程度,输出公共序列

#include <iostream>
#include <string>
using namespace std;int c[1000][1000]; //c[i][j]用来存储 Xi到Yj的最长公共子序列长度 void MaxLength(int m, int n, string x, string y) { //m,n分别表示字符串x和字符串y的长度 int i, j; for (i = 0; i <= m; i++) // 当j为0的时候,空序列是Xi到Yj的最长公共子序列,所以赋值0,注意这里i从0开始c[i][0] = 0;for (i = 0; i <= n; i++) // 当x为0的时候,空序列是Xi到Yj的最长公共子序列,所以赋值0,注意这里i从0开始c[0][i] = 0;for (i = 1; i <= m; i++) {  for (j = 1; j <= n; j++) { if (x[i - 1] == y[j - 1]) {  // 索引要减1,因为字符串从0开始c[i][j] = c[i - 1][j - 1] + 1;} else {c[i][j] = max(c[i - 1][j], c[i][j - 1]); }}} 
}void LCS(int i, int j, string x, string y) {if (i == 0 || j == 0) return;if (x[i - 1] == y[j - 1]) { LCS(i - 1, j - 1, x, y); cout << x[i - 1]; } else if (c[i - 1][j] >= c[i][j - 1]) {LCS(i - 1, j, x, y);} else {LCS(i, j - 1, x, y);}
}int main() {string x, y;cin >> x >> y;int m = x.length();  // 得到字符串x的长度 int n = y.length();   // 得到字符串y的长度 MaxLength(m, n, x, y); int precent = 0; if (c[m][n]!= 0) {precent = (c[m][n] * 100) / min(m, n);}cout << "公共长度:" << c[m][n] << endl; if (precent > 75) {cout << precent << "% " << "Yes,相似度高" << endl;} else {cout << precent << "% " << "No,相似度不高" << endl;}cout << "最长序列:" << endl; LCS(m, n, x, y);cout << endl;return 0;
}

相关文章:

LCS最长公共子序列C++实现

算法思路&#xff1a;动态规划 版本1&#xff1a;只输出公共长度 #include <iostream> #include <string> using namespace std;int c[1000][1000]; //c[i][j]用来存储 Xi到Yj的最长公共子序列长度 void MaxLength(int m, int n, string x, string y) { //m&#x…...

深入刨析数据结构之排序(上)

目录 1.内部排序 1.1概述 1.2插入排序 1.2.1其他插入排序 1.2.1.1 折半插入排序 1.2.1.2 2-路插入排序 1.3希尔排序 1.4快速排序 1.4.1起泡排序 1.4.2快速排序 1.4.2.1hoare版本 1.4.2.2挖坑版本 1.4.2.3前后指针版本 1.4.2.4优化版本 1.4.2.4.1小区间插入排序优…...

【无重复字符的最长子串】

一、题目 给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的 最长子串的长度。示例 1: 输入: s "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"&#xff0c;所以其长度为 3。示例 2: 输入: s "bbbbb" 输出: 1 解释: …...

Vue3+Element Plus的表格分页实战

Element Plus 是一个基于 Vue 3 的现代化 UI 组件库,旨在帮助开发者快速构建美观且功能丰富的 Web 应用程序。它提供了大量的 UI 组件,如按钮、表单、表格、弹出框、标签页、树形控件等,涵盖了 Web 应用开发中常见的大多数场景。本文通过一个实例来说明vue3+elementplus查询…...

vue项目搭建规范

项目搭建规范 一. 代码规范1.1. 集成editorconfig配置1.2. 使用prettier工具1.3. 使用ESLint检测1.4. git Husky和eslint1.5. git commit规范1.5.1. 代码提交风格1.5.2. 代码提交验证 二. 第三方库集成2.1. vue.config.js配置2.2. vue-router集成2.3. vuex集成2.4. element-plu…...

Mac iTerm2集成DeepSeek AI

1. 去deepseek官网申请api key&#xff0c;DeepSeek 2. 安装iTerm2 AI Plugin插件&#xff0c;https://iterm2.com/ai-plugin.html&#xff0c;插件解压后直接放到和iTerms相同的位置&#xff0c;默认就在/Applications 下 3. 配置iTerm2 4. 重启iTerm2,使用快捷键呼出AI对话…...

检索增强生成(RAG)

检索增强生成&#xff08;Retrieval-Augmented Generation, RAG&#xff09;是一种结合了检索机制和生成模型的先进技术&#xff0c;旨在提高自然语言处理系统的准确性和上下文相关性。本文将详细介绍如何从零开始构建一个RAG系统&#xff0c;包括数据处理、检索、生成以及部署…...

【第二部分--Python之基础】03 容器类型的数据

Python内置的数据类型如序列&#xff08;列表、元组等&#xff09;、集合和字典等可以容纳多项数据&#xff0c;我们称它们为容器类型的数据。 序列 序列&#xff08;sequence&#xff09;是一种可迭代的、元素有序的容器类型的数据。 序列包括列表&#xff08;list&#xff…...

【人工智能机器学习基础篇】——深入详解深度学习之复杂网络结构:卷积神经网络(CNN)、循环神经网络(RNN)、生成对抗网络(GAN)等概念及原理

深入详解深度学习之复杂网络结构&#xff1a;卷积神经网络&#xff08;CNN&#xff09;、循环神经网络&#xff08;RNN&#xff09;、生成对抗网络&#xff08;GAN&#xff09; 深度学习作为人工智能的重要分支&#xff0c;通过复杂的网络结构实现对数据的高级抽象和理解。本文…...

MySQL 入门教程

MySQL是最流行的关系型数据库管理系统&#xff0c;在WEB应用方面MySQL是最好的RDBMS(Relational Database Management System&#xff1a;关系数据库管理系统)应用软件之一。 在本教程中&#xff0c;会让大家快速掌握MySQL的基本知识&#xff0c;并轻松使用MySQL数据库。 什么…...

【sql】CAST(GROUP_CONCAT())实现一对多对象json输出

数据库&#xff1a;mysql 5.7版本以上 问题&#xff1a;一对多数据&#xff0c;实现输出一条数据&#xff0c;并将多条数据转换成json对象输出&#xff0c;可以实现一对多个字段。 项目中关系较为复杂&#xff0c;以下简化数据关系如下&#xff1a; t1是数据表&#xff0c;t…...

QT:控件属性及常用控件(1)------核心控件及属性

一个图形化界面上的内容&#xff0c;不需要我们直接从零去实现 QT中已经提供了很多的内置控件&#xff1a; 按钮&#xff0c;文本框&#xff0c;单选按钮&#xff0c;复选按钮&#xff0c;下拉框等等。。。。。 文章目录 1.常用控件属性1.1 enabled1.2 geometry1.2.1 geometry…...

使用 Python结合ffmpeg 实现单线程和多线程推流

一、引言 在本文中&#xff0c;我们将详细介绍如何使用 Python 进行视频的推流操作。我们将通过两个不同的实现方式&#xff0c;即单线程推流和多线程推流&#xff0c;来展示如何利用 cv2&#xff08;OpenCV&#xff09;和 subprocess 等库将视频帧推送到指定的 RTMP 地址。这…...

Linux一些问题

修改YUM源 Centos7将yum源更换为国内源保姆级教程_centos使用中科大源-CSDN博客 直接安装包&#xff0c;走链接也行 Index of /7.9.2009/os/x86_64/Packages 直接复制里面的安装包链接&#xff0c;在命令行直接 yum install https://vault.centos.org/7.9.2009/os/x86_64/Pa…...

在 Ubuntu 24.04.1 LTS | Python 3.12 环境下部署 Crypto 库

测试一些密码学方案需要用到 Crypto 库&#xff0c;网上教程大多针对 Windows 和 Python 3.10 或以下的环境&#xff0c;所以写下了这篇博文。 部署与使用 首先执行 su 输入密码进入超级用户&#xff0c;部署完 Python 3.12 环境后&#xff0c;执行以下命令进行安装&#xff…...

HTML5实现好看的二十四节气网页源码

HTML5实现好看的新年春节元旦网站源码 前言一、设计来源1.1 主界面1.2 关于我们界面1.3 春季节气界面1.4 夏季节气界面1.5 秋季节气界面1.6 冬季节气界面 二、效果和源码2.1 动态效果2.2 源代码 源码下载结束语 HTML5实现好看的二十四节气网页源码&#xff0c;春季节气&#xf…...

C++(9)—类和对象(上) ②实例化

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、实例化概念二、对象大小 1.对象存储2.内存对齐规则总结 前言 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、实例化概念 • …...

Effective C++读书笔记——item2(const,enum,inlines取代#define)

关于用常量取代 #define 的总体原则 在编程中&#xff0c;应尽量减少预处理器&#xff08;特别是 #define&#xff09;的使用&#xff0c;可通过合适的替代方式来避免 #define 带来的诸多问题&#xff0c;虽然不能完全消除预处理器相关指令&#xff08;如 #include、#ifdef/#i…...

如何科学评估与选择新版本 Python 编程语言和工具

文章目录 摘要引言评估新版本的关键因素适用性评估成本与收益分析 新版本功能的实际应用示例代码模块详细解析示例代码模块代码模块解析实际应用场景如何运行与配图 QA环节总结参考资料 摘要 随着技术的快速发展&#xff0c;编程语言和软件工具不断推出新版本&#xff0c;带来…...

第十届“挑战杯”大学生课外学术科技作品竞赛解析及资料

“挑战杯”被誉为大学生科技创新创业的“奥林匹克”盛会&#xff0c;它汇聚了来自各个学科、各个年级的精英人才。在这里&#xff0c;同学们带着对未知的好奇和对知识的渴望&#xff0c;组成一个个团队&#xff0c;向难题发起挑战。现在&#xff0c;第十届“挑战杯”大学生课外…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)

目录 &#x1f50d; 若用递归计算每一项&#xff0c;会发生什么&#xff1f; Horners Rule&#xff08;霍纳法则&#xff09; 第一步&#xff1a;我们从最原始的泰勒公式出发 第二步&#xff1a;从形式上重新观察展开式 &#x1f31f; 第三步&#xff1a;引出霍纳法则&…...

【AI News | 20250609】每日AI进展

AI Repos 1、OpenHands-Versa OpenHands-Versa 是一个通用型 AI 智能体&#xff0c;通过结合代码编辑与执行、网络搜索、多模态网络浏览和文件访问等通用工具&#xff0c;在软件工程、网络导航和工作流自动化等多个领域展现出卓越性能。它在 SWE-Bench Multimodal、GAIA 和 Th…...