最长公共子序列求长度和输出子序列C代码
求两个字符串的公共子序列我们都知道需要使用用动态规划思想
用res[i][j]表示截止到字符串A的第i个字符串和截止到字符串B的第j个字符的最长公共子序列。如两个字符串helloworld和loop,res[5][3]表示子串hello和子串loo的最长公共子序列,为lo,长度为2
状态转移方程
当i=0或j=0时,res[i][j]=0
当A[i]=B[j]时,res[i][j]= res[i-1][j-1]+1
当A[i]≠B[j]时,res[i][j]= max(res[i][j-1], res[i-1][j])
但是这样只能算出来最长公共子序列的长度,如果需要输出子序列的话需要用回溯的方法,比较难。我们可以用一个三维字符型数组来做动态规划数组,这样既能得到实际的公共子序列,也能得到长度
定义变量
char s1[105];
char s2[105];
char dp[105][105][105]; // 使用三维dp数组
具体实现
scanf("%s %s",s1,s2);
int i,j;
int n=strlen(s1);
int m=strlen(s2);
dp[0][0][0] = '\0'; // 初始化为空字符串for(i=1;i<=n;i++){for(j=1;j<=m;j++){if(s1[i-1]==s2[j-1]){strcpy(dp[i][j], dp[i-1][j-1]);int len = strlen(dp[i][j]);dp[i][j][len]=s1[i-1];dp[i][j][len+1]='\0';}else{int L1=strlen(dp[i-1][j]);int L2=strlen(dp[i][j-1]);if(L1>L2)strcpy(dp[i][j], dp[i-1][j]);elsestrcpy(dp[i][j], dp[i][j-1]);}}
}
printf("%d\n",len(dp[n][m])); //输出子序列的最大长度
printf("%s\n", dp[n][m]); //输出最大子序列
相关文章:
最长公共子序列求长度和输出子序列C代码
求两个字符串的公共子序列我们都知道需要使用用动态规划思想 用res[i][j]表示截止到字符串A的第i个字符串和截止到字符串B的第j个字符的最长公共子序列。如两个字符串helloworld和loop,res[5][3]表示子串hello和子串loo的最长公共子序列,为lo࿰…...
安卓Framework开发快速分析日志及定位源码
文章目录 如何区分源码中 main system events 日志查看 Activity 生命周期日志分析 events 日志在源码中位置应用进程ID助分析具体应用ProtoLog 动态开关日志如何快速定位相关流程的代码位置 本文首发地址 https://h89.cn/archives/285.html 最新更新地址 https://gitee.com/ch…...
数据结构算法之B树
一、绪论 1.1 数据结构的概念和作用 1.2 B树的起源和应用领域 二、B树的基本原理 2.1 B树的定义和特点 2.2 B树的结构和节点组成 2.3 B树的插入 2.4 B树的删除操作 三、B树的优势和应用 3.1 B树在数据库系统中的应用 3.2 B树在文件系统中的应用 3.3 B树在内存管理中…...
【图卷积网络】GCN基础原理简单python实现
基础原理讲解 应用路径 卷积网络最经典的就是CNN,其 可以提取图片中的有效信息,而生活中存在大量拓扑结构的数据。图卷积网络主要特点就是在于其输入数据是图结构数据,即 G ( V , E ) G(V,E) G(V,E),其中V是节点,E是…...
【话题】AI是在帮助开发者还是取代他们
大家好,我是全栈小5,欢迎阅读小5的系列文章,这是《话题》系列文章 目录 引言AI在代码生成中的应用AI在错误检测和自动化测试中的作用对开发者职业前景的影响技能需求的变化与适应策略结论文章推荐 引言 随着人工智能(AIÿ…...
精通Perl正则表达式修饰符:提升文本处理能力的艺术
Perl语言以其强大的文本处理能力而闻名,其中正则表达式是其核心特性之一。正则表达式本身非常强大,但Perl提供的修饰符(Modifiers)进一步扩展了正则表达式的灵活性和表达能力。本文将深入探讨Perl中正则表达式修饰符的使用&#x…...
【web前端HTML+CSS+JS】--- HTML学习笔记01
学习链接:黑马程序员pink老师前端入门教程,零基础必看的h5(html5)css3移动端前端视频教程_哔哩哔哩_bilibili 学习文档: Web 开发技术 | MDN (mozilla.org) 一、前后端工作流程 WEB模型:前端用于采集和展示信息,中…...
Go 语言入门(一)
Go Modules依赖包查找机制 下载的第三方的依赖存储在 $GOPATH/pkg/mod 下go install 生成的可执行文件存储在 $GOPATH/bin下依赖查找顺序: 工作目录$GOPATH/pkg/mod$GOPATH/src 一、Go语言基础 1.标识符与关键字 1.1 命名方式 go变量、常量、自定义类型、包…...
爬虫笔记20——票星球抢票脚本的实现
以下内容仅供交流学习使用!!! 思路分析 前面的爬虫笔记一步一步走过来我们的技术水平也有了较大的提升了,现在我们来进行一下票星球抢票实战项目,实现票星球的自动抢票。 我们打开票星球的移动端页面,分…...
DDR3(三)
目录 1 预取1.1 什么是预取1.2 预取有哪些好处1.3 结构框图1.4 总结 2 突发2.1 什么是突发2.2 突发与预取 本文讲解DDR中常见的两个术语:预取和突发,对这两个概念理解的关键在于地址线的低位是否参与译码,具体内容请继续往下看。 1 预取 1.1…...
JDK都出到20多了,你还不会使用JDK8的Stream流写代码吗?
目录 前言 Stream流 是什么? 为什么要用Steam流 常见stream流使用案例 映射 map() & 集合 collect() 单字段映射 多字段映射 映射为其他的对象 映射为 Map 去重 distinct() 过滤 filter() Stream流的其他方法 使用Stream流的弊端 前言 当你某天看…...
QT slots 函数
文章目录 概述小结 概述 在Qt中,slots 是一种特殊的成员函数,它们可以与对象发出的信号连接。当信号被触发时,连接的槽函数会被调用。 来个简单的示例吧,如下图: #include <QObject> #include <QDebug>…...
pycharm如何使用jupyter
目录 配置jupyter新建jupyter文件别人写的方法(在pycharm种安装,在网页中使用) pycharm专业版 配置jupyter 在pycharm终端启动一个conda虚拟环境,输入 conda install jupyter会有很多前置包需要安装: 新建jupyter…...
机器学习——无监督学习(k-means算法)
1、K-Means聚类算法 K表示超参数个数,如分成几个类别,K值就取多少。若无需求,可使用网格搜索找到最佳的K。 步骤: 1、随机设置K个特征空间内的点作为初始聚类中心; 2、对于其他每个点计算到K个中心的距离,…...
强化学习-6 DDPG、PPO、SAC算法
文章目录 1 DPG方法2 DDPG算法3 DDPG算法的优缺点4 TD3算法4.1 双Q网络4.2 延迟更新4.3 噪声正则 5 附15.1 Ornstein-Uhlenbeck (OU) 噪声5.1.1 定义5.1.2 特性5.1.3 直观理解5.1.4 数学性质5.1.5 代码示例5.1.6 总结 6 重要性采样7 PPO算法8 附28.1 重要性采样方差计算8.1.1 公…...
vue3实现多表头列表el-table,拖拽,鼠标滑轮滚动条优化
需求背景解决效果index.vue 需求背景 需要实现多表头列表的用户体验优化 解决效果 index.vue <!--/** * author: liuk * date: 2024-07-03 * describe:**** 多表头列表 */--> <template><el-table ref"tableRef" height"calc(100% - 80px)&qu…...
Micron近期发布了32Gb DDR5 DRAM
Micron Technology近期发布了一项内存技术的重大突破——一款32Gb DDR5 DRAM芯片,这项创新不仅将存储容量翻倍,还显著提升了针对人工智能(AI)、机器学习(ML)、高性能计算(HPC)以及数…...
SQL Server时间转换
第一种:format --转化成年月日 select format( GETDATE(),yyyy-MM-dd) --转化年月日,时分秒,这里的HH指24小时的,hh是12小时的 select format( GETDATE(),yyyy-MM-dd HH:mm:ss) --转化成时分秒的,这里就不一样的&…...
kubernetes集群部署:node节点部署和CRI-O运行时安装(三)
关于CRI-O Kubernetes最初使用Docker作为默认的容器运行时。然而,随着Kubernetes的发展和OCI标准的确立,社区开始寻找更专门化的解决方案,以减少复杂性和提高性能。CRI-O的主要目标是提供一个轻量级的容器运行时,它可以直接运行O…...
03:Spring MVC
文章目录 一:Spring MVC简介1:说说自己对于Spring MVC的了解?1.1:流程说明: 一:Spring MVC简介 Spring MVC就是一个MVC框架,Spring MVC annotation式的开发比Struts2方便,可以直接代…...
玩转springboot之springboot注册servlet
springboot注册servlet 有时候在springboot中依然需要注册servlet,filter,listener,就以servlet为例来进行说明,另外两个也都类似 使用WebServlet注解 在servlet3.0之后,servlet注册支持注解注册,而不需要在…...
推荐好玩的工具之OhMyPosh使用
解除禁止脚本 Set-ExecutionPolicy RemoteSigned 下载Oh My Posh winget install oh-my-posh 或者 Install-Module oh-my-posh -Scope AllUsers 下载Git提示 Install-Module posh-git -Scope CurrentUser 或者 Install-Module posh-git -Scope AllUser 下载命令提示 Install-Mo…...
pydub、ffmpeg 音频文件声道选择转换、采样率更改
快速查看音频通道数和每个通道能力判断具体哪个通道说话;一般能量大的那个算是说话 import wave from pydub import AudioSegment import numpy as npdef read_wav_file(file_path):with wave.open(file_path, rb) as wav_file:params wav_file.getparams()num_cha…...
0803实操-Windows Server系统管理
Windows Server系统管理 系统管理与基础配置 查看系统信息、更改计算机名称 网络配置 启用网络发现 Windows启用网络发现是指在网络设置中启用一个功能,该功能允许您的计算机在网络上识别和访问其他设备和计算机。具体来说,启用网络发现后ÿ…...
使用Java构建物联网应用的最佳实践
使用Java构建物联网应用的最佳实践 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 随着物联网(IoT)技术的快速发展,越来越…...
价格预言机的使用总结(一):Chainlink篇
文章首发于公众号:Keegan小钢 前言 价格预言机已经成为了 DeFi 中不可获取的基础设施,很多 DeFi 应用都需要从价格预言机来获取稳定可信的价格数据,包括借贷协议 Compound、AAVE、Liquity ,也包括衍生品交易所 dYdX、PERP 等等。…...
【Pyhton】读取寄存器数据到MySQL数据库
目录 步骤 modsim32软件配置 Navicat for MySQL 代码实现 步骤 安装必要的库:确保安装了pymodbus和pymysql。 配置Modbus连接:设置Modbus从站的IP地址、端口(对于TCP)或串行通信参数(对于RTU)。 连接M…...
jmeter-beanshell学习3-beanshell获取请求报文和响应报文
前后两个报文,后面报文要用前面报文的响应结果,这个简单,正则表达式或者json提取器,都能实现。但是如果后面报文要用前面请求报文的内容,感觉有点难。最早时候把随机数写在自定义变量,前后两个接口都用这个…...
【C++】B树及其实现
写目录 一、B树的基本概念1.引入2.B树的概念 二、B树的实现1.B树的定义2.B树的查找3.B树的插入操作4.B树的删除5.B树的遍历6.B树的高度7.整体代码 三、B树和B*树1.B树2.B*树3.总结 一、B树的基本概念 1.引入 我们已经学习过二叉排序树、AVL树和红黑树三种树形查找结构&#x…...
C++(Qt)-GIS开发-QGraphicsView显示瓦片地图简单示例
C(Qt)-GIS开发-QGraphicsView显示瓦片地图简单示例 文章目录 C(Qt)-GIS开发-QGraphicsView显示瓦片地图简单示例1、概述2、实现效果3、主要代码4、源码地址 更多精彩内容👉个人内容分类汇总 👈👉GIS开发 👈 1、概述 支持多线程加…...
CTFShow的RE题(三)
数学不及格 strtol 函数 long strtol(char str, char **endptr, int base); 将字符串转换为长整型 就是解这个方程组了 主要就是 v4, v9的关系, 3v9-(v10v11v12)62d10d4673 v4 v12 v11 v10 0x13A31412F8C 得到 3*v9v419D024E75FF(1773860189695) 重点&…...
WordPress主题开发进群付费主题v1.1.2 多种引流方式
全新前端UI界面,多种前端交互特效让页面不再单调,进群页面群成员数,群成员头像名称,每次刷新页面随机更新不重复,最下面评论和点赞也是如此随机刷新不重复 进群页面简介,群聊名称,群内展示&…...
SAP中的 UPDATA TASK 和 BACKGROUND TASK
前言: 记录这篇文章起因是调查生产订单报工问题引申出来的一个问题,后来再次调查后了解了其中缘由,大概记录以下,如有不对,欢迎指正。问题原贴如下: SAP CO11N BAPI_PRODORDCONF_CREATE_TT连续报工异步更…...
UDP协议:独特之处及其在网络通信中的应用
在网络通信领域,UDP(用户数据报协议,User Datagram Protocol)是一种广泛使用的传输层协议。与TCP(传输控制协议,Transmission Control Protocol)相比,UDP具有其独特的特点和适用场景…...
支持向量机(Support Vector Machine,SVM)及Python和MATLAB实现
支持向量机(Support Vector Machine,SVM)是一种经典的机器学习算法,广泛应用于模式识别、数据分类和回归分析等领域。SVM的背景可以追溯到1990s年代,由Vladimir Vapnik等人提出,并在之后不断发展和完善。 …...
【RT-thread studio 下使用STM32F103-学习sem-信号量-初步使用-线程之间控制-基础样例】
【RT-thread studio 下使用STM32F103-学习sem-信号量-初步使用-线程之间控制-基础样例】 1、前言2、环境3、事项了解(1)了解sem概念-了解官网消息(2)根据自己理解,设计几个使用方式(3)不建议运行…...
使用nodejs输出著作权申请所需的word版源码
使用nodejs输出著作权申请所需的word版源码 背景 软件著作权申请需要提供一份80页的word版源代码,如果手工复制源码到word文档中,工作量将无聊到让任何一个DAO人员血压爆表,因此我们不得不编写一个简单的文本处理代码,通过自动方…...
[Vite]vite-plugin-react和vite-plugin-react-swc插件原理了解
[Vite]vite-plugin-react和vite-plugin-react-swc插件原理了解 共同的作用 JSX 支持:插件为 React 应用程序中的 JSX 语法提供支持,确保它可以被正确地转换为 JavaScript。Fast Refresh:提供热更新功能,当应用程序在开发服务器上…...
记一次使用“try-with-resources“的语法导致的BUG
背景描述 最近使用try-catch的时候遇到了一个问题,背景是这样的:当第一次与数据库建立连接以后执行查询完毕并没有手动关闭连接,但是当我第二次获取连接的时候报错了,显示数据库连接失败,连接已经关闭。 org.postgres…...
用Excel处理数据图像,出现交叉怎么办?
一、问题描述 用excel制作X-Y散点图,意外的出现了4个交叉点,而实际上的图表数据是没有交叉的。 二、模拟图表 模拟部分数据,并创建X-Y散点图,数据区域,X轴数据是依次增加的,因此散点图应该是没有交叉的。…...
SpringBoot | 大新闻项目后端(redis优化登录)
该项目的前篇内容的使用jwt令牌实现登录认证,使用Md5加密实现注册,在上一篇:http://t.csdnimg.cn/vn3rB 该篇主要内容:redis优化登录和ThreadLocal提供线程局部变量,以及该大新闻项目的主要代码。 redis优化登录 其实…...
ESP32——物联网小项目汇总
商品级ESP32智能手表 [文章链接] 用ESP32,做了个siri?!开源了! [文章链接]...
flutter:监听路由的变化
问题 当从路由B页面返回路由A页面后,A页面需要进行数据刷新。因此需要监听路由变化 解决 使用RouteObserver进行录音监听 创建全局变量,不在任何类中 final RouteObserver<PageRoute> routeObserver RouteObserver<PageRoute>();在mai…...
Linux多进程和多线程(六)进程间通信-共享内存
多进程(六) 共享内存共享内存的创建 示例: 共享内存删除 共享内存映射 共享内存映射的创建解除共享内存映射示例:写入和读取共享内存中的数据 写入: ### 读取: 大致操作流程: 多进程(六) 共享内存 共享内存是将分配的物理空间直接映射到进程的⽤户虚拟地址空间中, 减少数据在…...
ruoyi后台修改
一、日志文件过大分包 \ruoyi-admin\src\main\resources\logback.xml <!-- 系统日志输出 --> <appender name"file_info" class"ch.qos.logback.core.rolling.RollingFileAppender"><file>${log.path}/sys-info.log</file><!…...
macOS查看系统日志的方法
1、command空格键打开搜索框,输入‘控制台’并打开 2、选择日志报告,根据日期打开自己需要的文件就可以...
数字信号处理及MATLAB仿真(3)——采样与量化
今天写主要来编的程序就是咱们AD变换的两个步骤。一个是采样,还有一个是量化。大家可以先看看,这一过程当中的信号是如何变化的。信号的变换图如下。 先说说采样,采样是将连续时间信号转换为离散时间信号的过程。在采样过程中,连续…...
云端AI大模型群体智慧后台架构思考
1 大模型的调研 1.1 主流的大模型 openai-chatgpt 阿里巴巴-通义千问 一个专门响应人类指令的大模型。我是效率助手,也是点子生成机,我服务于人类,致力于让生活更美好。 百度-文心一言(千帆大模型) 文心一言"…...
算法系列--分治排序|再谈快速排序|快速排序的优化|快速选择算法
前言:本文就前期学习快速排序算法的一些疑惑点进行详细解答,并且给出基础快速排序算法的优化版本 一.再谈快速排序 快速排序算法的核心是分治思想,分治策略分为以下三步: 分解:将原问题分解为若干相似,规模较小的子问题解决:如果子问题规模较小,直接解决;否则递归解决子问题合…...
强化学习编程实战-1-一个及其简单的强化学习实例(多臂赌博机)
1.1 多臂赌博机 一台拥有K个臂的机器,玩家每次可以摇动K个臂中的一个,摇动后,会吐出数量不等的金币,吐出金币的数量服从一定的概率分布,而且不同臂的概率分布不同。 多臂赌博机的问题是:假设玩家共有N次摇地…...