1、题目描述

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

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

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

2、代码详解

dp初始化问题：dp实际是存储最大公共子串的默认值的数组，初始化为0，因为假设都是不存在重复子串嘛！越界问题：但是要设置多少个0呢？我们考虑到i+1，所以必须设置为len(A)+1,这里有两个数组,故dp=[[0]*(len(B)+1) for _ in range(len(A)+1)],其实这可看作是矩阵的常用写法。状态：dp为A和B的最长公共前缀，转移方程：dp[i+1][j+1]=dp[i][j]+1。在此之后（断开后）有可能会有更长的重复子串，故以result更新dp最大值，若是断开之后将会重新从0开始算，这就是初始化为啥要设为0了！！模板：动态方程一般都采用dp[i+1][j+1]=dp[i][j]+1，dp[i+1][j+1]=max(dp[i][j-1],dp[i-1][j])等类似的形式，然后一般会用res=max(dp[i+1][j+1],res)，存储最终结果。 class Solution(object): def findLength(self, A, B): """ :type A: List[int] :type B: List[int] :rtype: int """ m = len(A) n = len(B) dp = [[0]*(n+1) for _ in range(m+1)] res = 0 for i in range(m): for j in range(n): if A[i] == B[j]: dp[i+1][j+1] = dp[i][j] + 1 res = max(res, dp[i+1][j+1]) # print(dp) return res A = [1,2,3,2,1] B = [3,2,1,4,7] s = Solution() print(s.findLength(A, B))

拓展（字符串，返回串和长度）

最长公共子串(The Longest Common Substring)  LCS问题就是求两个字符串最长公共子串的问题。

解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1,否则为0。

然后求出对角线最长的1的序列，其对应的位置就是最长匹配子串的位置。

''' 两个字符串，求最长连续公共子串。 s1:abcxdkscad s2:abkwkscawww 输出：ksca ''' def func(s1, s2): len_1 = len(s1) len_2 = len(s2) dp = [[0 for _ in range(len_2+1)] for _ in range(len_1+1)] nmax = 0 # 最长匹配的长度 p = 0 # 最长匹配对应在s1中的最后一位 for i in range(len_1): for j in range(len_2): if s1[i] == s2[j]: dp[i+1][j+1] = dp[i][j] + 1 if dp[i+1][j+1] > nmax: nmax = dp[i+1][j+1] p = i + 1 print(dp) return s1[p-nmax:p], nmax # 返回最长子串及其长度 s1 = 'abcxdkscad' s2 = 'abkwkscawww' print(func(s1, s2)) # ('ksca', 4)