最长连续公共子数组，子串，本科001

本文主要是介绍最长连续公共子数组，子串，本科001，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、描述

718最长连续公共子串，
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例：

输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1.1公共子串，非连续

的链接

2、关键字

最长，公共子串，连续

3、思路

经典dp,
按第一个串初始化第一行，遍历第一个串，与第二个串的首元素进行比较，如果相等就初始化为1，不等就初始化为0，
按第二个串初始化第一列，与第一个串的首元素比较，如果相等就初始化为1，不等就初始化为0，
然后两层循环遍历二维dp数组，把最大值搞出来输出就好了，

还有一个求两个字符串的最长公共子串，不要求连续，
只是不相等的时候当前值的处理不同，这个题是直接置0，而不连续的是取左边和上边的最大值，

相等的时候都是取左上元素+1

4、notes

连续

5、复杂度

时间O(NM）
空间O(NM）

6、code

class Solution {
public:int findLength(vector<int>& A, vector<int>& B) {int res=0;int n=A.size();  // 列数int m=B.size();  // 行数res=(A[0]==B[0])?1:0;  // res初始化二维数组的第一行第一列 abc  agt vector<vector<int>>dp(m,vector<int>(n,0));for(int i=0;i<n;i++){  // 初始化第一行if(A[i]==B[0]){dp[0][i]=1;}}for(int j=0;j<m;j++){  // 初始化第一列if(A[0]==B[j]){dp[j][0]=1;}}for(int i=1;i<m;i++){  // 填充剩下的二维数组for(int j=1;j<n;j++){if(B[i]==A[j]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=0;}res=max(res,dp[i][j]);}}return res;}
};

这篇关于最长连续公共子数组，子串，本科001的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---