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

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...

游戏开发中常见的战斗数值英文缩写对照表

游戏开发中常见的战斗数值英文缩写对照表 基础属性&#xff08;Basic Attributes&#xff09; 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...

Canal环境搭建并实现和ES数据同步

作者&#xff1a;田超凡 日期&#xff1a;2025年6月7日 Canal安装&#xff0c;启动端口11111、8082&#xff1a; 安装canal-deployer服务端&#xff1a; https://github.com/alibaba/canal/releases/1.1.7/canal.deployer-1.1.7.tar.gz cd /opt/homebrew/etc mkdir canal…...