最长重复子数组的最长公共前缀问题
字数 3363 2025-12-16 00:20:21

最长重复子数组的最长公共前缀问题

题目描述
给定两个整数数组 nums1 和 nums2，请找出两个数组中公共的、长度最长的“公共前缀子数组”。
“公共前缀子数组”定义为：从两个数组的某个起始位置 i 和 j 开始，长度均为 L 的子数组 nums1[i:i+L] 和 nums2[j:j+L] 完全相同，且这个公共子数组必须同时是两个数组各自从该位置开始的最长公共前缀。
更形式化地说，我们需要找到一个最大的长度 L，使得存在索引 i 和 j，满足：

  1. 对于所有 0 ≤ k < L，有 nums1[i + k] = nums2[j + k]。
  2. 在各自数组内，从 i 和 j 开始的子数组是各自数组从该位置起与另一数组匹配的最长前缀，即：
    • 对于 nums1，不存在更大的 L1 > L 使得 nums1[i:i+L1] 是 nums2[j:j+L1] 的前缀。
    • 对于 nums2，不存在更大的 L2 > L 使得 nums2[j:j+L2] 是 nums1[i:i+L2] 的前缀。
      实际上，这个问题可以简化为：寻找两个数组的所有公共子数组中，满足“从该位置开始是两数组的最长公共前缀”的最大长度。

示例：
nums1 = [1,2,3,4,5]
nums2 = [3,4,5,1,2]
一个候选是 i=2, j=0，对应子数组 [3,4,5]，长度 3，且从 nums1[2] 开始的 [3,4,5] 是 nums2[0:3] 的匹配，但 nums1[2:5] 是 [3,4,5] 而 nums2[0:5] 是 [3,4,5,1,2]，不匹配更长，所以 L=3 是从 i=2 和 j=0 开始的最长公共前缀。
另一个候选是 i=0, j=3，对应 [1,2] 长度 2。
最大长度是 3。

解题过程循序渐进讲解

步骤 1：问题理解与转化
题目的核心是“最长公共前缀子数组”，注意它不同于普通的最长公共子数组（可以不要求是前缀）。
普通最长公共子数组问题：给定 nums1[0..m-1] 和 nums2[0..n-1]，我们用 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组长度，转移方程：

如果 nums1[i-1] == nums2[j-1] 则 dp[i][j] = dp[i-1][j-1] + 1
否则 dp[i][j] = 0

最终答案是所有 dp[i][j] 的最大值。

但本题要求：这个公共子数组必须是从 i 和 j 开始的最长公共前缀。
也就是说，当我们找到一个匹配 nums1[i] = nums2[j] 时，我们看从它开始能匹配多长，这个匹配长度就是满足 nums1[i+k] = nums2[j+k] 的最大 k。
这其实就是求两数组从任意位置 (i, j) 开始的最长公共前缀长度（LCP length）。
那么，我们只需要对所有 (i, j) 计算 LCP 长度，取最大值即可。
因为“从该位置开始是两数组的最长公共前缀”这个条件已经隐含在“LCP 长度”定义中。

结论：本题转化为：求所有 (i, j) 的 LCP 长度，取最大值。
其中 LCP 长度定义为：从 i 和 j 开始，最多连续多少个元素相等。

步骤 2：暴力法
最直观的方法是枚举所有 i 和 j，对每个 (i, j) 向后扫描直到不匹配，记录长度，更新最大值。
时间复杂度 O(m * n * min(m, n))，在数组长度较大时不可行。

我们需要优化到 O(m * n)。

步骤 3：动态规划思路
设 dp[i][j] 表示：从 nums1 的第 i 个位置和 nums2 的第 j 个位置开始的最长公共前缀的长度。
注意这里的定义是“从 i 和 j 开始”，而不是“以 i 和 j 结尾”。
转移方程：
如果 nums1[i] == nums2[j]，则 dp[i][j] = 1 + dp[i+1][j+1]。
如果 nums1[i] != nums2[j]，则 dp[i][j] = 0。
我们需要计算所有的 i 从 m-1 到 0，j 从 n-1 到 0。
最终答案 = 所有 dp[i][j] 的最大值。

为什么这样可行？
因为 dp[i][j] 表示从 i 和 j 开始的匹配长度，那么当当前字符相等时，长度等于从下一个位置开始的匹配长度加 1。
这类似于后缀匹配的经典 DP。

步骤 4：动态规划实现细节

  1. 初始化 dp 为二维数组，大小为 (m+1) x (n+1)，多一行一列是为了让 i=m 或 j=n 时表示越界，长度为 0。
  2. 遍历顺序：从后往前，i 从 m-1 到 0，j 从 n-1 到 0。
  3. 转移： 
    如果 nums1[i] == nums2[j]:
    dp[i][j] = dp[i+1][j+1] + 1
否则:
    dp[i][j] = 0
  4. 在计算过程中记录 max(dp[i][j])。

步骤 5：举例说明
nums1 = [1,2,3,4,5]
nums2 = [3,4,5,1,2]
m=5, n=5。
建立 dp[6][6]，初始最后一列和最后一行全 0。
从 i=4 到 0，j=4 到 0 计算：

i=4: nums1[4]=5
j=4: nums2[4]=2 → 不相等 → dp[4][4]=0
j=3: nums2[3]=1 → 不等 → 0
j=2: nums2[2]=5 → 相等 → dp[4][2]=dp[5][3]+1=0+1=1
j=1: nums2[1]=4 → 不等 → 0
j=0: nums2[0]=3 → 不等 → 0

i=3: nums1[3]=4
j=4: 2 → 不等 → 0
j=3: 1 → 不等 → 0
j=2: 5 → 不等 → 0
j=1: 4 → 相等 → dp[3][1]=dp[4][2]+1=1+1=2
j=0: 3 → 不等 → 0

i=2: nums1[2]=3
j=4: 2 → 不等 → 0
j=3: 1 → 不等 → 0
j=2: 5 → 不等 → 0
j=1: 4 → 不等 → 0
j=0: 3 → 相等 → dp[2][0]=dp[3][1]+1=2+1=3

继续计算 i=1, i=0 会发现没有比 3 更大的值。
所以答案是 3。

步骤 6：复杂度分析
时间复杂度 O(m * n)，因为每个状态计算是 O(1)。
空间复杂度 O(m * n)，可以优化到 O(n) 或 O(min(m, n))，因为我们只依赖下一行的下一列，可以用滚动数组优化。
但为了清晰，我们先用二维数组讲解。

步骤 7：滚动数组优化
因为 dp[i][j] 只依赖 dp[i+1][j+1]，我们可以用一维数组从后往前更新。
设 dp[j] 表示当前行 i 的 dp[i][j] 值。
我们还需要一个变量 prev 来记录 dp[i+1][j+1] 的旧值。
具体更新顺序：
对 i 从 m-1 到 0：
初始化 next 为 0（表示 dp[i+1][n]）
对 j 从 n-1 到 0：
temp = dp[j] // 保存上一行 dp[i+1][j] 的值（在更新前它是上一行的结果）
如果 nums1[i] == nums2[j]：
dp[j] = next + 1 // next 是上一轮 dp[i+1][j+1]
否则：
dp[j] = 0
next = temp // 这个 temp 成为下一轮的 dp[i+1][j]
更新答案

这样空间复杂度 O(n)。

步骤 8：最终答案
在 DP 过程中不断更新最大值即可。
注意最终答案是所有 dp[i][j] 的最大值，它就是我们要求的“最长公共前缀子数组”的长度，因为定义上 dp[i][j] 就是从 i 和 j 开始的最长公共前缀长度。

这样就完成了本题的线性动态规划解法。

最长重复子数组的最长公共前缀问题 题目描述 给定两个整数数组 nums1 和 nums2 ，请找出两个数组中公共的、长度最长的“公共前缀子数组”。 “公共前缀子数组”定义为：从两个数组的某个起始位置 i 和 j 开始，长度均为 L 的子数组 nums1[i:i+L] 和 nums2[j:j+L] 完全相同，且这个公共子数组必须同时是两个数组各自从该位置开始的最长公共前缀。 更形式化地说，我们需要找到一个最大的长度 L ，使得存在索引 i 和 j ，满足： 对于所有 0 ≤ k < L ，有 nums1[i + k] = nums2[j + k] 。 在各自数组内，从 i 和 j 开始的子数组是各自数组从该位置起与另一数组匹配的最长前缀，即： 对于 nums1 ，不存在更大的 L1 > L 使得 nums1[i:i+L1] 是 nums2[j:j+L1] 的前缀。 对于 nums2 ，不存在更大的 L2 > L 使得 nums2[j:j+L2] 是 nums1[i:i+L2] 的前缀。 实际上，这个问题可以简化为：寻找两个数组的所有公共子数组中，满足“从该位置开始是两数组的最长公共前缀”的最大长度。 示例： nums1 = [1,2,3,4,5] nums2 = [3,4,5,1,2] 一个候选是 i=2, j=0 ，对应子数组 [3,4,5] ，长度 3，且从 nums1[2] 开始的 [3,4,5] 是 nums2[0:3] 的匹配，但 nums1[2:5] 是 [3,4,5] 而 nums2[0:5] 是 [3,4,5,1,2] ，不匹配更长，所以 L=3 是从 i=2 和 j=0 开始的最长公共前缀。 另一个候选是 i=0, j=3 ，对应 [1,2] 长度 2。 最大长度是 3。 解题过程循序渐进讲解 步骤 1：问题理解与转化 题目的核心是“最长公共前缀子数组”，注意它不同于普通的最长公共子数组（可以不要求是前缀）。 普通最长公共子数组问题：给定 nums1[0..m-1] 和 nums2[0..n-1] ，我们用 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组长度，转移方程： 最终答案是所有 dp[i][j] 的最大值。 但本题要求：这个公共子数组必须是从 i 和 j 开始的最长公共前缀。 也就是说，当我们找到一个匹配 nums1[i] = nums2[j] 时，我们看从它开始能匹配多长，这个匹配长度就是满足 nums1[i+k] = nums2[j+k] 的最大 k 。 这其实就是求两数组从任意位置 (i, j) 开始的最长公共前缀长度（LCP length）。 那么，我们只需要对所有 (i, j) 计算 LCP 长度，取最大值即可。 因为“从该位置开始是两数组的最长公共前缀”这个条件已经隐含在“LCP 长度”定义中。 结论 ：本题转化为：求所有 (i, j) 的 LCP 长度，取最大值。 其中 LCP 长度定义为：从 i 和 j 开始，最多连续多少个元素相等。 步骤 2：暴力法 最直观的方法是枚举所有 i 和 j ，对每个 (i, j) 向后扫描直到不匹配，记录长度，更新最大值。 时间复杂度 O(m * n * min(m, n))，在数组长度较大时不可行。 我们需要优化到 O(m * n)。 步骤 3：动态规划思路 设 dp[i][j] 表示： 从 nums1 的第 i 个位置和 nums2 的第 j 个位置开始的最长公共前缀的长度 。 注意这里的定义是“从 i 和 j 开始”，而不是“以 i 和 j 结尾”。 转移方程： 如果 nums1[i] == nums2[j] ，则 dp[i][j] = 1 + dp[i+1][j+1] 。 如果 nums1[i] != nums2[j] ，则 dp[i][j] = 0 。 我们需要计算所有的 i 从 m-1 到 0 ， j 从 n-1 到 0 。 最终答案 = 所有 dp[i][j] 的最大值。 为什么这样可行？ 因为 dp[i][j] 表示从 i 和 j 开始的匹配长度，那么当当前字符相等时，长度等于从下一个位置开始的匹配长度加 1。 这类似于后缀匹配的经典 DP。 步骤 4：动态规划实现细节 初始化 dp 为二维数组，大小为 (m+1) x (n+1) ，多一行一列是为了让 i=m 或 j=n 时表示越界，长度为 0。 遍历顺序：从后往前， i 从 m-1 到 0 ， j 从 n-1 到 0 。 转移： 在计算过程中记录 max(dp[i][j]) 。 步骤 5：举例说明 nums1 = [1,2,3,4,5] nums2 = [3,4,5,1,2] m=5, n=5。 建立 dp[6][6] ，初始最后一列和最后一行全 0。 从 i=4 到 0，j=4 到 0 计算： i=4: nums1[ 4 ]=5 j=4: nums2[ 4]=2 → 不相等 → dp[ 4][ 4 ]=0 j=3: nums2[ 3 ]=1 → 不等 → 0 j=2: nums2[ 2]=5 → 相等 → dp[ 4][ 2]=dp[ 5][ 3 ]+1=0+1=1 j=1: nums2[ 1 ]=4 → 不等 → 0 j=0: nums2[ 0 ]=3 → 不等 → 0 i=3: nums1[ 3 ]=4 j=4: 2 → 不等 → 0 j=3: 1 → 不等 → 0 j=2: 5 → 不等 → 0 j=1: 4 → 相等 → dp[ 3][ 1]=dp[ 4][ 2 ]+1=1+1=2 j=0: 3 → 不等 → 0 i=2: nums1[ 2 ]=3 j=4: 2 → 不等 → 0 j=3: 1 → 不等 → 0 j=2: 5 → 不等 → 0 j=1: 4 → 不等 → 0 j=0: 3 → 相等 → dp[ 2][ 0]=dp[ 3][ 1 ]+1=2+1=3 继续计算 i=1, i=0 会发现没有比 3 更大的值。 所以答案是 3。 步骤 6：复杂度分析 时间复杂度 O(m * n)，因为每个状态计算是 O(1)。 空间复杂度 O(m * n)，可以优化到 O(n) 或 O(min(m, n))，因为我们只依赖下一行的下一列，可以用滚动数组优化。 但为了清晰，我们先用二维数组讲解。 步骤 7：滚动数组优化 因为 dp[i][j] 只依赖 dp[i+1][j+1] ，我们可以用一维数组从后往前更新。 设 dp[j] 表示当前行 i 的 dp[i][j] 值。 我们还需要一个变量 prev 来记录 dp[i+1][j+1] 的旧值。 具体更新顺序： 对 i 从 m-1 到 0： 初始化 next 为 0（表示 dp[i+1][n] ） 对 j 从 n-1 到 0： temp = dp[j] // 保存上一行 dp[i+1][j] 的值（在更新前它是上一行的结果） 如果 nums1[i] == nums2[j] ： dp[j] = next + 1 // next 是上一轮 dp[i+1][j+1] 否则： dp[j] = 0 next = temp // 这个 temp 成为下一轮的 dp[i+1][j] 更新答案 这样空间复杂度 O(n)。 步骤 8：最终答案 在 DP 过程中不断更新最大值即可。 注意最终答案是所有 dp[i][j] 的最大值，它就是我们要求的“最长公共前缀子数组”的长度，因为定义上 dp[i][j] 就是从 i 和 j 开始的最长公共前缀长度。 这样就完成了本题的线性动态规划解法。