最长重复子串（最长公共子串的变种——允许最多k次不匹配的最长重复子串）
字数 2994 2025-12-06 00:04:45

最长重复子串（最长公共子串的变种——允许最多k次不匹配的最长重复子串）

题目描述
给定两个字符串 s 和 t，以及一个整数 k。请找出一个最长的子串，使得这个子串是 s 的某个子串，同时在 t 中存在一个子串，这两个子串最多有 k 个位置上的字符不同。返回这个最长子串的长度。

举例说明

  • 输入：s = "abcde", t = "abzde", k = 1
    输出：5
    解释：最长子串是 "ab_de"（_ 表示不匹配位置）。在 s 中是 "abcde"，在 t 中是 "abzde"，只有第3个字符不同（'c' vs 'z'），不匹配数 1 <= k。

  • 输入：s = "abcd", t = "efgh", k = 0
    输出：0
    解释：没有任何相同字符，无法找到满足条件的子串。

解题思路
这是一个二维动态规划问题，是经典最长公共子串（Longest Common Substring）的变种。在经典问题中，dp[i][j] 表示以 s[i-1] 和 t[j-1] 结尾的最长公共子串的长度。本题增加了“最多允许 k 个位置不匹配”的条件，因此状态定义需扩展，以记录当前子串中的不匹配数量。

定义状态
dp[i][j][m] 表示以 s 的第 i 个字符结尾、以 t 的第 j 个字符结尾的子串中，不匹配字符数量恰好为 m 的最长子串长度。但这样空间复杂度为 O(n³)，可能过高。我们优化为二维状态：

我们可以枚举所有可能的子串起始位置偏移，转化为一维问题：固定子串在 s 中的起始位置 i 和在 t 中的起始位置 j，然后向右扩展，统计不匹配数，直到不匹配数超过 k 时停止。但这样是 O(n³) 时间复杂度，不够高效。

更优的解法是使用二维动态规划，定义 dp[i][j] 表示以 s[i-1] 和 t[j-1] 结尾的子串中，不匹配字符的数量。但经典最长公共子串的 dp[i][j] 只记录长度，这里需要同时记录不匹配数和长度。为此，我们可以用两个二维数组：len[i][j] 表示以 s[i-1] 和 t[j-1] 结尾的子串长度，diff[i][j] 表示这个子串中的不匹配字符数。但这两个值不独立，递推较复杂。

实际上，更直观的方法是使用“距离函数”：对于每一对起始位置 (i, j)，计算从该位置开始向后扩展，使得不匹配数不超过 k 的最大长度。这可以通过滑动窗口（双指针）在线性时间内完成。对所有起始位置组合执行，总复杂度 O(n²)。但注意字符串长度较长时可能依然较高。

动态规划递推
我们采用改进的二维动态规划，结合二分搜索优化时间复杂度：

  1. 定义 f[i][j] 表示以 s[i-1] 和 t[j-1] 结尾的子串，在满足不匹配数不超过 k 的条件下，能向左扩展的最大长度。但直接递推困难，因为不匹配数的累加与之前的选择有关。

  2. 常见技巧是，将问题转化为：寻找最大长度 L，使得存在一对起始位置 (i, j)，子串 s[i:i+L-1] 和 t[j:j+L-1] 的不匹配数 ≤ k。这是一个判定性问题，可以用二分搜索解决。

算法步骤

步骤1：二分搜索最长长度

  • 设定搜索范围 [0, min(n, m)]，其中 n、m 分别是 s 和 t 的长度。
  • 每次猜测长度 mid，检查是否存在长度为 mid 的子串满足条件。

步骤2：检查函数 check(mid)
检查是否存在长度为 mid 的子串，其不匹配数 ≤ k。

  • 方法：遍历 s 中所有长度为 mid 的子串，计算它们与 t 中所有长度为 mid 的子串的最少不匹配数。但直接比较是 O(n * m * mid)，太慢。
  • 优化：使用动态规划计算不匹配数。定义 dp[i][j] 表示子串 s[i-mid+1:i] 和 t[j-mid+1:j] 的不匹配数。但这样仍是 O(nm) 每次检查。
  • 更优：使用滚动哈希（Rabin-Karp）将子串匹配转化为哈希比较，但需要允许不匹配。可以用二分+哈希，但实现复杂。

步骤3：动态规划直接解法
实际上，我们可以直接通过二维动态规划在 O(nm) 内求解，无需二分。定义状态：

dp[i][j] 表示以 s[i-1] 和 t[j-1] 结尾的子串，在最多允许 k 个不匹配的前提下，能取得的最大长度。但这样无法直接递推，因为 dp[i][j] 依赖于前面连续匹配的情况。

我们换一种状态：diff[i][j] 表示以 s[i-1] 和 t[j-1] 结尾的子串中，不匹配字符的数量。但我们需要的是长度。因此，可以定义 len[i][j] 表示以 s[i-1] 和 t[j-1] 结尾的子串，在当前不匹配数不超过 k 的前提下，能向左延伸的最大长度。但 len[i][j] 与 diff[i][j] 需要同时更新。

最终解法：使用前缀和优化不匹配统计
设 pre[i][j] 表示子串 s[0:i-1] 和 t[0:j-1] 中对应位置是否匹配（匹配为0，不匹配为1）。但这是二维前缀和，不方便。

更简洁：对于每对起始偏移 (dx)，我们将问题转化为一维数组，然后使用滑动窗口求最大长度。具体：

  • 枚举偏移量 dx = i - j，其中 dx ∈ [-m+1, n-1]。
  • 对于每个 dx，构造一个序列 arr，其中 arr[p] = 0 如果 s[i] == t[j]，否则为 1。这里 i 和 j 满足 i - j = dx 且 i, j 在有效范围内。
  • 然后在 arr 上找最长的子数组，使得元素和 ≤ k。这就是经典的最大满足条件的子数组问题，用滑动窗口在 O(L) 内解决，L 是该偏移下的有效位置数。
  • 总复杂度 O((n+m) * min(n,m))，即 O(nm) 最坏，但平均更好。

步骤4：滑动窗口求最长满足条件的子数组
对于每个偏移 dx，得到序列 arr 后，用双指针 left, right 滑动窗口，保持窗口内 arr 的和 ≤ k，记录最大窗口长度。

举例说明
s = "abcde", t = "abzde", k = 1
偏移 dx=0 时，对应位置 (0,0),(1,1),(2,2),(3,3),(4,4)
arr = [0,0,1,0,0] （比较 s[2]='c' 和 t[2]='z' 不匹配）
滑动窗口：最大长度 5（整个数组和=1 ≤ k）。

步骤5：复杂度分析

  • 时间：O((n+m) * min(n,m))。每个偏移生成 arr 需要 O(min(n,m))，滑动窗口 O(min(n,m))，总 O((n+m)*min(n,m)) ≤ O(nm)。
  • 空间：O(min(n,m)) 存储 arr。

总结
这道题本质是最长公共子串的“带容错”版本。通过枚举偏移转化为一维数组，再用滑动窗口求最大子数组和 ≤ k 的长度。避免了三维动态规划的高复杂度，实现了较优解法。

最长重复子串（最长公共子串的变种——允许最多k次不匹配的最长重复子串） 题目描述 给定两个字符串 s 和 t ，以及一个整数 k 。请找出一个最长的子串，使得这个子串是 s 的某个子串，同时在 t 中存在一个子串，这两个子串最多有 k 个位置上的字符不同。返回这个最长子串的长度。 举例说明 输入： s = "abcde" , t = "abzde" , k = 1 输出：5 解释：最长子串是 "ab_de" （ _ 表示不匹配位置）。在 s 中是 "abcde" ，在 t 中是 "abzde" ，只有第3个字符不同（ 'c' vs 'z' ），不匹配数 1 <= k 。 输入： s = "abcd" , t = "efgh" , k = 0 输出：0 解释：没有任何相同字符，无法找到满足条件的子串。 解题思路 这是一个二维动态规划问题，是经典最长公共子串（Longest Common Substring）的变种。在经典问题中， dp[i][j] 表示以 s[i-1] 和 t[j-1] 结尾的最长公共子串的长度。本题增加了“最多允许 k 个位置不匹配”的条件，因此状态定义需扩展，以记录当前子串中的不匹配数量。 定义状态 dp[i][j][m] 表示以 s 的第 i 个字符结尾、以 t 的第 j 个字符结尾的子串中，不匹配字符数量恰好为 m 的最长子串长度。但这样空间复杂度为 O(n³)，可能过高。我们优化为二维状态： 我们可以枚举所有可能的子串起始位置偏移，转化为一维问题：固定子串在 s 中的起始位置 i 和在 t 中的起始位置 j ，然后向右扩展，统计不匹配数，直到不匹配数超过 k 时停止。但这样是 O(n³) 时间复杂度，不够高效。 更优的解法是使用二维动态规划，定义 dp[i][j] 表示以 s[i-1] 和 t[j-1] 结尾的子串中，不匹配字符的数量。但经典最长公共子串的 dp[i][j] 只记录长度，这里需要同时记录不匹配数和长度。为此，我们可以用两个二维数组： len[i][j] 表示以 s[i-1] 和 t[j-1] 结尾的子串长度， diff[i][j] 表示这个子串中的不匹配字符数。但这两个值不独立，递推较复杂。 实际上，更直观的方法是使用“距离函数”：对于每一对起始位置 (i, j) ，计算从该位置开始向后扩展，使得不匹配数不超过 k 的最大长度。这可以通过滑动窗口（双指针）在线性时间内完成。对所有起始位置组合执行，总复杂度 O(n²)。但注意字符串长度较长时可能依然较高。 动态规划递推 我们采用改进的二维动态规划，结合二分搜索优化时间复杂度： 定义 f[i][j] 表示以 s[i-1] 和 t[j-1] 结尾的子串，在满足不匹配数不超过 k 的条件下，能向左扩展的最大长度。但直接递推困难，因为不匹配数的累加与之前的选择有关。 常见技巧是，将问题转化为：寻找最大长度 L，使得存在一对起始位置 (i, j) ，子串 s[i:i+L-1] 和 t[j:j+L-1] 的不匹配数 ≤ k。这是一个判定性问题，可以用二分搜索解决。 算法步骤 步骤1：二分搜索最长长度 设定搜索范围 [0, min(n, m)] ，其中 n、m 分别是 s 和 t 的长度。 每次猜测长度 mid ，检查是否存在长度为 mid 的子串满足条件。 步骤2：检查函数 check(mid) 检查是否存在长度为 mid 的子串，其不匹配数 ≤ k。 方法：遍历 s 中所有长度为 mid 的子串，计算它们与 t 中所有长度为 mid 的子串的最少不匹配数。但直接比较是 O(n * m * mid)，太慢。 优化：使用动态规划计算不匹配数。定义 dp[i][j] 表示子串 s[i-mid+1:i] 和 t[j-mid+1:j] 的不匹配数。但这样仍是 O(nm) 每次检查。 更优：使用滚动哈希（Rabin-Karp）将子串匹配转化为哈希比较，但需要允许不匹配。可以用二分+哈希，但实现复杂。 步骤3：动态规划直接解法 实际上，我们可以直接通过二维动态规划在 O(nm) 内求解，无需二分。定义状态： dp[i][j] 表示以 s[i-1] 和 t[j-1] 结尾的子串，在最多允许 k 个不匹配的前提下，能取得的最大长度。但这样无法直接递推，因为 dp[ i][ j ] 依赖于前面连续匹配的情况。 我们换一种状态： diff[i][j] 表示以 s[i-1] 和 t[j-1] 结尾的子串中，不匹配字符的数量。但我们需要的是长度。因此，可以定义 len[i][j] 表示以 s[i-1] 和 t[j-1] 结尾的子串，在当前不匹配数不超过 k 的前提下，能向左延伸的最大长度。但 len[i][j] 与 diff[i][j] 需要同时更新。 最终解法：使用前缀和优化不匹配统计 设 pre[i][j] 表示子串 s[0:i-1] 和 t[0:j-1] 中对应位置是否匹配（匹配为0，不匹配为1）。但这是二维前缀和，不方便。 更简洁：对于每对起始偏移 (dx) ，我们将问题转化为一维数组，然后使用滑动窗口求最大长度。具体： 枚举偏移量 dx = i - j ，其中 dx ∈ [-m+1, n-1] 。 对于每个 dx ，构造一个序列 arr ，其中 arr[p] = 0 如果 s[i] == t[j] ，否则为 1。这里 i 和 j 满足 i - j = dx 且 i, j 在有效范围内。 然后在 arr 上找最长的子数组，使得元素和 ≤ k。这就是经典的最大满足条件的子数组问题，用滑动窗口在 O(L) 内解决，L 是该偏移下的有效位置数。 总复杂度 O((n+m) * min(n,m))，即 O(nm) 最坏，但平均更好。 步骤4：滑动窗口求最长满足条件的子数组 对于每个偏移 dx，得到序列 arr 后，用双指针 left, right 滑动窗口，保持窗口内 arr 的和 ≤ k，记录最大窗口长度。 举例说明 s = "abcde", t = "abzde", k = 1 偏移 dx=0 时，对应位置 (0,0),(1,1),(2,2),(3,3),(4,4) arr = [ 0,0,1,0,0] （比较 s[ 2]='c' 和 t[ 2 ]='z' 不匹配） 滑动窗口：最大长度 5（整个数组和=1 ≤ k）。 步骤5：复杂度分析 时间：O((n+m) * min(n,m))。每个偏移生成 arr 需要 O(min(n,m))，滑动窗口 O(min(n,m))，总 O((n+m)* min(n,m)) ≤ O(nm)。 空间：O(min(n,m)) 存储 arr。 总结 这道题本质是最长公共子串的“带容错”版本。通过枚举偏移转化为一维数组，再用滑动窗口求最大子数组和 ≤ k 的长度。避免了三维动态规划的高复杂度，实现了较优解法。