当前位置: 首页 > 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;第十届“挑战杯”大学生课外…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...