动态规划--最长公共子串
最长公共子串
- 公共子串问题
- 费曼算法
- 动态规划算法思路
- 代码实现
公共子串问题
在计算机科学中,最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的,而子串却必须是。链接: 百度百科
费曼算法
The Feynman Algorithm:
- Write down the problem.
- Think real hard.
- Write down the solution.
动态规划算法思路
-
给定两个字符串T1和T2, 假设dp(i, j)表示T1,T2在位置i, j的公共子串的长度【向位置0的方向,连续相同的字符的数量】
比如“abcdefg”, “absecde”
dp(0,0) = 1 ‘a’ == ‘a’
dp(1,1) = 2 ‘ab’ == ‘ab’
dp(1,2) = 0 ‘b’ != ‘s’ -
总结规律:
if T1[i] == T2[j] :
dp(i,j) = dp(i-1,j-1) + 1
else:
dp(i,j) = 0
代码实现
def getLcs(t1:str, t2:str)->str:'''get the longest common substring of two given string'''if not t1:return t1if not t2:return t2# dp = [[0 for i in range(len(t2)+1)] for j in range(len(t1)+1)]max_len = 0dp = [[0 for i in range(len(t2)+1)] for j in range(2)]for i in range(1, len(t1)+1):ind = [0,1][i%2==0]for j in range(1, len(t2)+1):if t1[i-1]==t2[j-1]:dp[ind][j] = dp[1-ind][j-1] + 1else:dp[ind][j] = 0if dp[ind][j] >max_len:max_len = dp[ind][j]p = iprint("max_len:%d , pos: %d"%(max_len,p))return t1[p-max_len:p]
相关文章:
动态规划--最长公共子串
最长公共子串公共子串问题费曼算法动态规划算法思路代码实现公共子串问题 在计算机科学中,最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的,而子串却必须是。链接: 百度百科 费曼算法…...

【运筹优化】剩余空间法求解带顺序约束的二维矩形装箱问题 + Java代码实现
文章目录一、带顺序约束的二维矩形装箱问题二、剩余空间法三、完整代码实现3.1 Instance 实例类3.2 Item 物品类3.3 PlaceItem 已放置物品类3.4 Solution 结果类3.5 RSPackingWithWeight 剩余空间算法类3.6 Run 运行类3.7 测试案例3.8 ReadDataUtil 数据读取类3.9 运行结果展示…...

第四阶段15-关于权限,处理解析JWT时的异常,跨域请求,关于Spring Security的认证流程
处理解析JWT时的异常 由于解析JWT是在过滤器中执行的,而过滤器是整个服务器端中最早接收到所有请求的组件,此时,控制器等其它组件尚未运行,则不可以使用此前的“全局异常处理器”来处理解析JWT时的异常(全局异常处理器…...

毕业设计 基于51单片机的指纹红外密码电子锁
基于51单片机的指纹红外密码电子锁1、项目简介1.1 系统框架1.2 系统功能2、部分电路设计2.1 STC89C52单片机最小系统电路设计2.2 矩阵按键电路电路设计2.3 液晶显示模块电路设计3、部分代码展示3.1 LCD12864显示字符串3.2 串口初始化实物图1、项目简介 选题指导,项…...

【JavaWeb】数据链路层协议——以太网 + 应用层协议——DNS
以太网 以太网不是一个具体的网络,而是一个技术标准,主要应用于数据链路层和物理层。 以太网数据帧结构 以太网的数据帧结构由三部分构成: 帧头 载荷 帧尾 其中的MAC地址是六位,这样就比IPV4所表示的地址大很多,…...
docker 容器安装 python jre
Dockerfile FROM python:2.7.11-alpine RUN mkdir /usr/local/java WORKDIR /usr/local/java # 5.更改 Alpine 的软件源为阿里云,默认从官方源拉取比较慢 RUN echo http://mirrors.aliyun.com/alpine/v3.10/main/ > /etc/apk/repositories && \ echo…...
Linux下将C++程序打包成动态库静态库方法
之前在这篇文章里介绍过动态库和静态库的理论部分,这篇文章主要介绍下实际的操作步骤: 静态链接库生成 gcc -c main.cpp -o main.o ar -rc libmain.a main.o sudo cp libmain.a /usr/local/lib 调用即可解释一下上面的命令:前两步生成了libmain.a sudo…...

Centos7 服务器基线检查处理汇总
1、服务器超时设置 问题描叙 TMOUT的值大于key2且小于等于{key2}且小于等于key2且小于等于{key1}视为合规 查看命令:export检测结果 超时时间:0处理方式 备份/etc/profile文件 cp /etc/profile /etc/profile_bak编辑profile文件 vim /etc/profile修改/新增 TMO…...

PaddleOCR遇到 lanms-neo问题处理
在window环境中安装PaddleOCR依赖是真的蛋疼,关键官方论坛里也都没有具体的解决方案。吐槽。。。吐槽。。。 我在 “windows安装lanms-neo问题处理”文章中看到lanms-neo问题全过程解决。个人觉得文档说明不是很细致,导致我按步骤执行,还是安…...

coreldraw2023安装包下载及新功能介绍
对于广告标识业来说 coreldraw这个软件,对我们来说绝对不陌生,我从2008年开始接触到广告制作,到现在已经13多年了,从一开始的coreldraw 9红色的热气球开始。就被这个强大的软件所吸引,他有强大的排榜功能已经对位图的处…...

Nginx 负载均衡服务失败场景
nginx可以配置负载均衡,我们可以通过配置实现nginx负载均衡。这里部署了两个服务producter-one和producter-one2。 upstream proxyproducter-one {server producter-one:8080 weight1;server producter-one2:8080 weight1;}# 访问其他服务server {listen 9090…...

开学季哪个电容笔好?2023口碑最好电容笔推荐
虽说苹果原装的电容笔非常好用,性能也非常不错,但由于价格昂贵,普通的学生是没办法购买的,再加上重量比较大,使用时间长了,难免会让人感觉到疲劳。如果仅仅是为了学习记笔记,那就没必要再去购买…...
经验分享-如何使用http调用chatGPT-3.5-turbo模型API
今天上午,就在工作群里收到了关于openAI发布chatGPT官方模型的消息分享。openAI这次的动作真的很快啊,没想到这么快就直接发布了chatGPT目前所使用的模型api。据Open AI在官方消息,本次开放了ChatGPT和Whisper的模型API,可以供用户…...
【C#】yyyy-MM-dd HH:mm:ss 时间格式 时间戳 全面解读超详细
C# 日期转字符串 实例化一个时间字符串 DateTimeFormatInfo dfInfonew DateTimeFormatInfo(); dfInfo.ShortDatePattern "yyyy/MM/dd hh:mm:ss:ffff"; DateTime dt Convert.ToDateTime("2019/07/01 18:18:18:1818", dfInfo);日期转字符串 string dat…...

基于神经网络的滑模鲁棒控制
目录 前言 1.双关节机械手臂模型 2.神经网络自适应律设计 3. 滑模控制律设计 4. 仿真分析 4.1 仿真模型 4.2 仿真结果 4.3 小结 5 学习问题 前言 上一篇文章我介绍了神经网络补偿的机理,只不过控制律不同,本章我们结合滑模理论设计控制律&#…...

2023年融资融券研究报告
第一章 行业概况 融资融券是证券交易市场上的两种金融衍生品交易方式,主要用于股票、债券等证券的融资和投资。 融资是指投资者向证券公司借入资金购买证券,以期望股票价格上涨后卖出获得利润。融资需支付一定的利息和费用,利息根据借入的资…...

Nodejs环境配置 | Linux安装nvm | windows安装nvm
文章目录一. 前言二. Linux Nodejs环境配置1. 安装nvm2. 配置npm三. Windows Nodejs环境配置1. 安装nvm2. 配置npm四. nvm基本使用一. 前言 由于在实际开发中一些不同的项目需要不同的npm版本来启动,所以本篇文章会基于nvm这个node版本管理工具来进行Linux和Winodw…...

显示接口测试
背景需求两个显示器连接到一台PC,期望每台显示器可以单独显示,在一台显示器显示时,另外一台显示器同PC的连接断开,即系统下查看到连接状态为disconnected。同时在显示器上图形化显示当前显示器编号。如下图,期望当显示…...

Tcl_Init error: Can‘t find a usable init.tcl in the following directories
目录 问题 解决 小结 问题 最近在研究开源波形显示软件gtkwave时,Ubuntu18.04下编译打包完成,移植到另一个电脑上运行时,出现以下错误,如图: 擦掉的部分是一些路径信息,这个错误提示意味着您的系统中缺少所需的 Tcl 初始化文件,路径下确实没有init.tcl文…...

进程控制(详解)
进程控制上篇文章介绍了进程的相关概念,形如进程的内核数据结构task_struct 、进程是如何被操作系统管理的、进程的查看、进程标识符、进程状态、进程优先级、已经环境变量和进程地址空间等知识点; 本篇文章接着上篇文章继续对进程的控制进行展开&#x…...

Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...

基于单片机的宠物屋智能系统设计与实现(论文+源码)
本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢,连接红外测温传感器,可实时精准捕捉宠物体温变化,以便及时发现健康异常;水位检测传感器时刻监测饮用水余量,防止宠物…...
计算机系统结构复习-名词解释2
1.定向:在某条指令产生计算结果之前,其他指令并不真正立即需要该计算结果,如果能够将该计算结果从其产生的地方直接送到其他指令中需要它的地方,那么就可以避免停顿。 2.多级存储层次:由若干个采用不同实现技术的存储…...