LeetCode.718.Maximum Length of Repeated Subarray 最长公共子串/最长重复子数组

题目描述

718 Maximum Length of Repeated Subarray
https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation:
The repeated subarray with maximum length is [3, 2, 1].

Note:
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

---

相似题目

LeetCode.1143.Longest Common Subsequence 最长公共子序列LCS
LeetCode.718.Maximum Length of Repeated Subarray 最长公共子串/最长重复子数组
LeetCode.300.Longest Increasing Subsequence 最长上升子序列LIS

---

解题过程

注意区分 最长公共子序列 Longest Common Substring 和 最长公共子串 Longest Common Subsequence，子序列 Subsequence 不要求连续，子串 Substring 必须是连续的。

动态规划

设 lcs[i,j] 是序列 Xi=<x1, x2, …, xi> 和 Yj=<y1, y2, …, yj> 的以 xi 和 yj 为结尾的(即必须包含xi和yj)最长公共子串的长度。
由于子串要求必须是连续的，其实也就是 xi,…,xm 和 yj,…,yn 的最长公共前缀。
所以，当 xi 和 yj 相等时，就能和前面的接上，以 xi 和 yj 为结尾的最长公共子串就是以 xi-1 和 yj-1 为结尾的最长公共子串的长度加1
当 xi 和 yj 不等时，以 xi 和 yj 为结尾的最长公共子串的长度就是0
对比
LeetCode.053.Maximum Subarray 最大连续子序列和
题，可以发现，当遇到连续子序列时，递推公式中一定是以xx为结尾的，因为只有这样才能和前面连续的接上。
或者可以这样对比子串和子序列：
由于子序列不连续，所以 dp[i][j] 可以从 dp[i-1][j] 或 dp[i][j-1] 转移过来，
由于子串必须连续，所以 dp[i][j] 只能从 dp[i-1][j-1] 转移。
而且，
子序列问题中，由于可以不连续，lcs[m][n] 就是最终结果。
但子串问题中，最终的结果并不是 lcs[m][n] ，而需要在递推的过程中不断更新最大值，也就是 lcs[0…m][0…n] 的最大值

所以

$
lcs[i,j] =
\begin{cases}
0, & \text{if $i = 0$ or $j = 0$ or $x_i \neq y_j$ } \\
cls[i-1, j-1] + 1, & \text{if $i,j > 0$ and $x_i = y_j$ } \\
\end{cases}
$

时间复杂度 O(mn)，空间复杂度 O(mn)

private static class SolutionV2020 {
    public int findLength(int[] A, int[] B) {
        if (null == A || A.length == 0 || null == B || B.length == 0) {
           return 0;
        }
        // lcs[i][j] 表示 text1[0...i-1] 和 text2[0...j-1] 的以 text1[i-1],text2[j-1] 为结尾(必须包含)的最长公共子串的长度
        int[][] lcs = new int[A.length + 1][B.length + 1];
        // lcsStr[i][j] 表示 text1[0...i-1] 和 text2[0...j-1] 的以 text1[i-1],text2[j-1] 为结尾(必须包含)的最长公共子串
        String[][] lcsStr = new String[A.length + 1][B.length + 1];
        // A,B的最长公共子串长度
        int lcsMax = 0;
        // A,B的最长公共子串
        String lcsStrMax = "";

        for (int i = 0; i <= A.length; i++) {
            for (int j = 0; j <= B.length; j++) {
                if (i ==0 || j== 0) {
                    lcs[i][j] = 0;
                    lcsStr[i][j] = "";
                    continue;
                }
                if (A[i-1] == B[j-1]) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                    lcsStr[i][j] = lcsStr[i - 1][j - 1] + A[i-1];
                    // 递推过程中要不断更新当前最大值
                    if (lcs[i][j] > lcsMax) {
                        lcsMax = lcs[i][j];
                        lcsStrMax = lcsStr[i][j];
                    }
                } else {
                    lcs[i][j] = 0;
                    lcsStr[i][j] = "";
                }
            }
        }
        System.out.println(lcsStrMax);
        return lcsMax;
    }
}

滑动窗口

将字符串s1和s2分别写在两把直尺上面，然后将s1固定，s2的尾部和s1的头部对齐，然后逐渐向右移动直尺s2，比较重叠部分的字符串中的公共子串的长度，直到直尺s2的头部移动到s1的尾部。在这个过程中求得的最大长度就是s1、s2最大子串的长度。

滑动窗口法

图片来自
https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/wu-li-jie-fa-by-stg-2/

程序员面试100题之七：最长公共子字符串
https://blog.csdn.net/hackbuteer1/article/details/6686931

---

GitHub代码

algorithms/leetcode/leetcode/_718_MaximumLengthOfRepeatedSubarray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_718_MaximumLengthOfRepeatedSubarray.java

---