首页 > 其他分享 >线性dp:最长公共子串

线性dp:最长公共子串

时间:2024-08-23 13:48:08浏览次数:10  
标签:子串 int 公共 线性 递推 最长 dp

最长公共子串

  • 本文讲解的题与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;
}

标签:子串,int,公共,线性,递推,最长,dp
From: https://www.cnblogs.com/Tomorrowland/p/18369780

相关文章

  • 线性代数
    看了很多题目,个人觉得现阶段以考察矩阵乘法(快速幂)、高斯消元法求线性方程组的解、矩阵优化dp、一些trick(线段树维护矩阵,kmp套矩阵等)以及矩阵自身性质的深层次运用为主。P1962斐波那契数列应该是典题。从这道题我们可以发现矩阵优化dp的最有效办法是手模,所以此类题目一般......
  • dp
    前情提要dp专题复习树形dp其实对我来说树形dp会比序列dp学得好一些,因为树是有一个具体形态的东西,推式子是比较具象的。其实序列就是把树拍平在数轴上去dp的,只要考虑到这一点,画出dp的转移图,式子就可以呼之欲出了。不套路的dp考验人类智慧的时刻到了!P1352没有上司......
  • python socket编辑示例 UDP
    服务端:fromsocketimportsocket,AF_INET,SOCK_DGRAMrecv_socket=socket(AF_INET,SOCK_DGRAM)recv_socket.bind(('127.0.0.1',8888))whileTrue:data,addr=recv_socket.recvfrom(1024)#接收数据print('客户说:',data.decode('......
  • 4-线性回归
    python中*运算符的使用用于将可迭代对象(如列表或元组)的元素解压缩为单独的参数当我们从Dataloader取出来的时候,又会将压缩为的单独参数分开importtorchfromtorch.utilsimportdata#准备数据true_w=torch.tensor([2,-3.4])true_b=4.2defsynthetic_data(w,b......
  • Little Bird(单调队列优化的DP)
    题目描述有一排\(n\)棵树,第\(i\)棵树的高度是\(d_i\)。有一只鸟要从第\(1\)棵树飞到第\(n\)棵树。如果鸟降落在第\(i\)棵树,那么它下一步可以降落到第\(i+1,i+2,\dots,i+k\)棵树之中的一棵。如果鸟降落到一棵不矮于当前树的树,那么它的劳累值会\(+1\),否则不会。求劳累值的最小值......
  • 线性回归(Linear Regression)
    一、损失(Loss)类型:L1损失【Re】:对模型对各个样本的预测的绝对误差求和。平均绝对误差(MAE)【Re】:一组样本L1损失的平均值。L2损失:【Re】对模型【Re】对各个样本的预测的误差的平方求和。均方误差【Re】:一组样本的L2 损失的平均值。如果数据中特征值超过了一定范围,或者模......
  • 计数DP
    闲话NFLS。话说AT计数dp好题挺多啊。[ABC248F]KeepConnect题解区已经讲得十分清楚了。套路地搞dp,将连通载入其中。\(dp_{i,j,0/1}\)表示前\(i\)列,断了\(j\)条边,上下是否连通的方案数。这里我们保证所有的点都与第\(i\)列其中的\(1\)或两个点相连。然后就可以转......
  • 网络通信(TCP+UDP通信)
    一、UDP协议 1.1、recvfrom()参数说明intsockfd,//socket的fdvoid*buf,//保存数据的一块空间的地址size_tlen,//这块空间的大小intflags,//0默认的接收方式-----阻塞方式默认行为是阻塞a.MSG_DONTWAIT不阻塞方式,用他的话代表读的时候是非阻塞方式b.类似......
  • C# start thread include Thread,Task,Async/Await,BackgroundWorker,ThreadPool,Time
    usingSystem;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Linq;usingSystem.Text;usingSystem.Threading;usingSystem.Threading.Tasks;usingSystem.Windows;usingSystem.Windows.Controls;usingSystem.Windows.Data;using......
  • 预设型DP
    我们设\(f[i][j][k]\)表示填到\(i\)个数,目前拓展出\(j\)个可以填数的区间(最两边不算,注意是可以填数的区间!!),贡献和为\(k\)。这个是可以填数的区间我们按从小到大进行填数。那么对于任意一个数x显然有三种情况。1.如果x左右目前都没数,那么说明它的左右两个数都比x大,此......