ToB企服应用市场:ToB评测及商务社交产业平台

标题: 线性dp：最长公共子串 [打印本页]

---

作者: 张裕    时间: 2024-8-24 10:55
标题: 线性dp：最长公共子串
最长公共子串

• 本文讲解的题与leetcode718.最长重复子数组，题意千篇一律，阅读完本文以后可以去挑衅这题。
  

力扣链接
题目叙述：

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

1. ABACCB
2. AACCAB

复制代码

输出

1. 3

复制代码

解释

最长公共子串是ACC，其长度为3。
与最长公共子序列的区别

• 公共子串：字符必须是连续相称的
  
• 公共子序列：字符必须是相称的，可以不连续。
  

动态规划思路

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

状态变量以及其含义

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

递推公式

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

遍历顺序：

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

怎样初始化？

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

举例打印dp数组

• 举例如如图所示：
  

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

最终代码实现

[code]#include#includeusing namespace std;char a[200]="BCCABCCB";char b[200]="AACCAB";int f[201][201];int main(){  int ans=0;  for(int i=1; i

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4