当前位置: 首页 > news >正文

动态规划--最长公共子串

最长公共子串

  • 公共子串问题
  • 费曼算法
  • 动态规划算法思路
    • 代码实现

公共子串问题

在计算机科学中,最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的,而子串却必须是。链接: 百度百科

费曼算法

The Feynman Algorithm:

  1. Write down the problem.
  2. Think real hard.
  3. Write down the solution.

动态规划算法思路

  1. 给定两个字符串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’

  2. 总结规律:
    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…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

【Android】Android 开发 ADB 常用指令

查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...