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

教育轻创合伙人模式成为教育行业新风口的原因与市场空间解析

随着教育行业数字化转型的加速&#xff0c;传统教育模式面临成本高、扩张慢等挑战。在此背景下&#xff0c;教育轻创合伙人模式应运而生&#xff0c;正迅速成为教育行业的新风口。这一模式通过低门槛、高灵活性的合作方式&#xff0c;有效打开了教育市场的增量空间。本文将深入…...

3个高效技巧:用Elsevier Tracker实现投稿状态智能监控

3个高效技巧&#xff1a;用Elsevier Tracker实现投稿状态智能监控 【免费下载链接】Elsevier-Tracker 项目地址: https://gitcode.com/gh_mirrors/el/Elsevier-Tracker 你是否也曾经历过这样的科研日常&#xff1a;每天打开Elsevier投稿系统&#xff0c;重复登录、点击…...

零基础友好:借助快马生成的指导项目轻松完成anaconda安装与初体验

最近在学Python数据分析&#xff0c;被各种环境配置搞得头大。朋友推荐用Anaconda管理环境&#xff0c;但光是安装就卡了半天。后来在InsCode(快马)平台发现了个神器项目&#xff0c;像有个老师手把手教操作&#xff0c;分享下我的学习过程&#xff1a; 为什么选择Anaconda 刚开…...

暗黑破坏神2存档编辑器终极指南:3步掌握可视化修改技巧

暗黑破坏神2存档编辑器终极指南&#xff1a;3步掌握可视化修改技巧 【免费下载链接】d2s-editor 项目地址: https://gitcode.com/gh_mirrors/d2/d2s-editor 还在为暗黑破坏神2存档修改而烦恼吗&#xff1f;传统的十六进制编辑不仅操作复杂&#xff0c;还容易导致存档损…...

3大核心功能:智慧树网课自动化学习解决方案

3大核心功能&#xff1a;智慧树网课自动化学习解决方案 【免费下载链接】zhihuishu 智慧树刷课插件&#xff0c;自动播放下一集、1.5倍速度、无声 项目地址: https://gitcode.com/gh_mirrors/zh/zhihuishu 诊断学习痛点 在线教育平台在提供便利的同时&#xff0c;也带来…...

Super Qwen Voice World效果展示:砖块跳动节拍与语音时长精准匹配

Super Qwen Voice World效果展示&#xff1a;砖块跳动节拍与语音时长精准匹配 1. 引言&#xff1a;当像素世界“开口说话” 想象一下&#xff0c;你正在玩一款复古的像素游戏。屏幕底部的砖块随着背景音乐有节奏地上下跳动&#xff0c;突然&#xff0c;一个充满活力的声音响起…...

10个HTTPie CLI高级功能实战技巧:从入门到精通API调试

10个HTTPie CLI高级功能实战技巧&#xff1a;从入门到精通API调试 【免费下载链接】cli &#x1f967; HTTPie CLI — modern, user-friendly command-line HTTP client for the API era. JSON support, colors, sessions, downloads, plugins & more. 项目地址: https:/…...

G-Helper终极指南:华硕笔记本轻量级控制工具完全教程

G-Helper终极指南&#xff1a;华硕笔记本轻量级控制工具完全教程 【免费下载链接】g-helper Lightweight, open-source control tool for ASUS laptops and ROG Ally. Manage performance modes, fans, GPU, battery, and RGB lighting across Zephyrus, Flow, TUF, Strix, Sca…...

Native代码与Java的交互艺术——访问字段、调用方法

在 Android 开发、高性能计算或遗留系统整合中&#xff0c;Java 与 Native 代码&#xff08;C/C&#xff09;的交互&#xff08;JNI&#xff09;是不可或缺的技能。本文将以实战为导向&#xff0c;详细讲解如何在 Native 层访问 Java 对象字段、调用实例与静态方法、处理字符串…...

实时操作系统(RTOS)核心特性与工业实践解析

1. 实时操作系统核心特性解析实时操作系统&#xff08;RTOS&#xff09;的核心设计理念在于"确定性响应"&#xff0c;这与我们日常使用的通用操作系统有着本质区别。我曾参与过工业控制系统的开发&#xff0c;深刻体会到RTOS在关键任务场景下的不可替代性。以数控机床…...