最长公共子序列求长度和输出子序列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方便,可以直接代…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
