首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

线性dp:最长公共子串

编程知识
2024年08月24日 10:40

最长公共子串

  • 本文讲解的题与leetcode718.最长重复子数组,题意一模一样,阅读完本文以后可以去挑战这题。

力扣链接

题目叙述:

给定两个字符串,输出其最长公共子串的长度。

输入

ABACCB
AACCAB

输出

3

解释

最长公共子串是ACC,其长度为3。

与最长公共子序列的区别

  • 公共子串:字符必须是连续相等的
  • 公共子序列:字符必须是相等的,可以不连续。

动态规划思路

  • 只有当两个字符串中的字符连续相等的时候,公共子串的长度才不断增加,否则清零
  • 因此,我们不难发现,公共子串问题其实是公共子序列问题的一个特殊情况

状态变量以及其含义

  • 我们延续最长公共子序列的思路,可以使用两个指针变量,ij来遍历a,b字符串。
  • 那么我们的f[i][j]代表着什么呢?因为本题是要连续的子串,因此我们的 f[i][j]表示以a[i]b[j]为结尾的公共子串的长度

递推公式

  • 那么,我们很容易的就可以得出递推公式:
    • f[i][j]=f[i-1][j-1]+1a[i]==b[j]
    • f[i][j]=0)(a[i]!=b[j]
  • 边界条件为:
    • f[0][j]=0
    • f[i][0]=0

遍历顺序:

  • 显然是从上到下,从左到右。

如何初始化?

  • 处理好上面所说的边界条件,并且根据递推公式来进行初始化f数组即可。

举例打印dp数组

  • 举例如如图所示:

img

  • f[i][j] 的值如图所示。

最终代码实现

#include<iostream>
#include<cstring>
using namespace std;

char a[200]="BCCABCCB";
char b[200]="AACCAB";
int f[201][201];

int main(){
  int ans=0;
  for(int i=1; i<=strlen(a); i++){
    for(int j=1; j<=strlen(b); j++){
      if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1]+1;
      ans=max(ans,f[i][j]);
    }
  }
  printf("ans=%d\n",ans);
  return 0;
}
From:https://www.cnblogs.com/Tomorrowland/p/18377581
本文地址: http://www.shuzixingkong.net/article/1397
0评论
提交 加载更多评论
其他文章 折腾 Quickwit,Rust 编写的分布式搜索引擎(专为从对象存储中实现亚秒级搜索而设计)
什么是 Quickwit? Quickwit 是首个能在云端存储上直接执行复杂的搜索与分析查询的引擎,并且具有亚秒级延迟。它借助 Rust 语言和分离计算与存储的架构设计,旨在实现资源高效利用、易于操作以及能够扩展到 PB 级数据量。 Quickwit 非常适合日志管理、分布式追踪以及通常为不可变数
折腾 Quickwit,Rust 编写的分布式搜索引擎(专为从对象存储中实现亚秒级搜索而设计) 折腾 Quickwit,Rust 编写的分布式搜索引擎(专为从对象存储中实现亚秒级搜索而设计)
从网友探秘 《黑神话:悟空》 的脚本说说C#
《黑神话:悟空》千呼万唤始出来。在正式发售后不到24小时,Steam在线玩家峰值突破222万,在Steam所有游戏在线玩家历史峰值中排名第二。第一拨玩家纷纷晒出好评,称这款现象级产品正式开启国产3A游戏(3A 俗称:大量的资源、大量的金钱和大量的时间)元年,黑神话悟空是国内首款3A游戏,画面剧情都很
从网友探秘 《黑神话:悟空》 的脚本说说C#
C++11新特性(二):语言特性
C++11新特性 语言特性 nullptr空指针 nullptr空指针的使用可以规避掉以往设置为NULL的风险。NULL在编译器中常常被设置为0或者其它数字,此时判断指针是否为NULL,即判断指针类型是否能够等于整型值,并不安全。 int *p = nullptr; 强类型枚举 强类型枚举不能隐式转
索引的使用
5年之后 祺源开发Java开发的时候才有使用索引的感觉。索引 面试中是十分频繁地被问到。索引分为聚簇索引和非聚簇索引。 古至今,人类都是 文盲到文明的演变过程。书籍的使用,文字的发明和记载信息。当文字量一大,翻阅查找起来就越困难。把相似的东西放 一起,使用标签标记存放,找起来更快。 索引和ID的概念
Go 互斥锁 Mutex 源码分析(二)
原创文章,欢迎转载,转载请注明出处,谢谢。 0. 前言 在 Go 互斥锁 Mutex 源码分析(一) 一文中分析了互斥锁的结构和基本的抢占互斥锁的场景。在学习锁的过程中,看的不少文章是基于锁的状态解释的,个人经验来看,从锁的状态出发容易陷入细节,了解锁的状态转换过一段时间就忘,难以做到真正的理解。想
Go 互斥锁 Mutex 源码分析(二) Go 互斥锁 Mutex 源码分析(二) Go 互斥锁 Mutex 源码分析(二)
PG数据库导致断电/重启无法正常启动问题排查
PG数据库导致断电/重启无法正常启动问题排查 一、问题 数据库断电后,启动PG数据库后无法正常启动,报”psql: could not connect to server: No such file or directory”的错误,错误图片如下: 二、背景分析 数据库是单机版,使用k8s进行部署运
PG数据库导致断电/重启无法正常启动问题排查 PG数据库导致断电/重启无法正常启动问题排查 PG数据库导致断电/重启无法正常启动问题排查
【Azure Logic App】在逻辑应用中开启或关闭一个工作流是否会对其它工作流产生影响呢?
问题描述 使用标准版的Azure Logic App服务,可以创建多个工作流(workflow),如果在启用/禁用其它的工作流时,是否会对正在运行其它工作流造成影响呢? 问题解答 在实际的测验中,我们得到的答案是:会造成影响!在Disabled/Enabled同一个Logic App中的Workfl
【Azure Logic App】在逻辑应用中开启或关闭一个工作流是否会对其它工作流产生影响呢? 【Azure Logic App】在逻辑应用中开启或关闭一个工作流是否会对其它工作流产生影响呢? 【Azure Logic App】在逻辑应用中开启或关闭一个工作流是否会对其它工作流产生影响呢?
AD(Active Directory )域的搭建与操作
AD 域的搭建与操作 一、准备工作 准备好 VM 虚拟机和 Server 的安装包。 二、安装 Server 2022 选择标准且有图形界面的进行安装。 选择自定义安装方式。 为虚拟机 server2022 安装 VMware tools。 回到桌面,右键个性化把计算机和网络图标放出来。 三、安装