最长重复子串（后缀数组解法与动态规划结合的变种：带k次不匹配的最长重复子串）
字数 4450 2025-12-13 22:50:44

最长重复子串（后缀数组解法与动态规划结合的变种：带k次不匹配的最长重复子串）

题目描述

给定一个字符串 \(s\) \，和一个整数 \(k\) 。你需要找到最长的重复子串，其中“重复”意味着在字符串中至少出现两次，且这两个出现位置允许最多有 \(k\) 个字符不同（即汉明距离不超过 \(k\) ）。子串可以由任意起始和结束位置定义，但同一个子串在不同位置出现时，只要其对应位置字符不同不超过 \(k\) 次，就算作符合条件的重复子串。求满足条件的最长子串的长度。

示例
输入：
s = "abacba"
k = 1
输出：3
解释：最长重复子串可以是 "aba"（位置0-2 和 位置2-4，"a b a" 与 "a b a" 距离0，但此处 "aba" 在位置2-4 是 "cba"？实际上需要检查：位置0-2: "aba"，位置3-5: "cba"，距离为2 > k，不满足）。实际上更合适的例子是 "ab" 在位置0-1 和 位置3-4，距离0，长度2，但存在长度3的子串吗？检查 "bac" 在位置1-3 和位置2-4："bac" vs "acb" 距离2 > k，不满足。但如果我们取 "ba" 在位置1-2 和 位置4-5，是 "ba" vs "ba" 距离0，长度2。但输出为3，说明存在长度3的重复子串，比如 "aba" 在位置0-2 和 位置4-6? 但字符串长度为6，没有位置6。所以我们重新看示例：
更清晰的示例：
s = "abcabc", k=1
输出可能是3，因为 "abc" 在位置0-2 和位置3-5 完全相同，距离0，长度3。
本题目标：找到最长的子串，使得字符串中存在两个起始位置 i 和 j（i ≠ j），子串 s[i:i+len] 和 s[j:j+len] 最多有 k 个对应字符不同。

解题过程（循序渐进讲解）

步骤1：问题理解与暴力法思路

我们要求的是最长长度 len，使得存在两个起始位置 i, j，满足对于长度 len 的子串，对应字符不同的个数 ≤ k。
暴力法：枚举所有子串长度（从大到小尝试），对每个长度 L，检查是否存在这样的 i, j。
检查方法：枚举所有 i, j，比较 s[i:i+L] 和 s[j:j+L] 的不同字符数是否 ≤ k。
时间复杂度：枚举长度 O(n)，枚举起始位置 O(n²)，比较 O(n)，总 O(n⁴)，太高。

步骤2：基于后缀数组的快速比较

如果知道两个子串的起始位置 i, j，如何快速比较它们长度为 L 的对应字符？
我们可以用“后缀”的概念：子串 s[i:i+L] 是后缀 suffix(i) 的长度为 L 的前缀。
后缀数组（Suffix Array）能将所有后缀排序，并且通过最长公共前缀（LCP）数组，可以快速知道两个后缀的公共前缀长度。
但这里我们需要的是“最多 k 个不同”，而非完全相等，所以 LCP 不能直接解决，但可以帮助减少比较次数。

思路：

  1. 构建后缀数组 SA 和 LCP 数组。
  2. 对任意两个后缀 suffix(SA[p]) 和 suffix(SA[q])，它们的最长公共前缀长度是 min(LCP[p+1], LCP[p+2], ..., LCP[q])（假设 p<q）。
  3. 但我们要找的是两个长度固定为 L 的子串，允许 k 个不同。这相当于在排序的后缀中，寻找两个后缀，使得它们的前 L 个字符中，不同字符数 ≤ k。

步骤3：转化为滑动窗口最大值问题

我们固定长度 L，想知道是否存在 i, j 使得子串 s[i:i+L] 和 s[j:j+L] 最多 k 个不同。
换个思路：我们枚举子串的起始位置 i，看是否存在另一个 j 满足条件。但更高效的是用后缀数组：

将所有后缀按字典序排序，那么如果两个后缀的公共前缀很长，它们会在排序后靠近。
对于长度 L 的窗口，我们可以在后缀数组中滑动一个宽度为 w 的窗口，使得窗口内所有后缀的长度为 L 的前缀彼此相差不大，但还是要比较不同字符数。

更好的方法（结合动态规划/预计算）：
定义 diff(i, j) 为 s[i:i+L] 和 s[j:j+L] 的汉明距离。
我们想要 diff(i, j) ≤ k。

预计算 diff 是 O(n²) 的，但我们可以用 DP 思想：
diff(i, j) 可以通过前缀和快速计算吗？
如果定义 same(i, j) = 1 如果 s[i] = s[j]，否则 0，那么 diff(i, j) = L - ∑_{t=0}^{L-1} same(i+t, j+t)。
这需要 O(L) 时间，依然大。

步骤4：二分答案 + 滚动哈希/后缀数组检查

常见技巧：二分查找长度 L。
如果存在长度为 L 的子串满足条件，那么更短的也一定存在（不一定，但我们可以用二分找最大 L）。
检查函数 check(L)：是否存在 i, j 使得 s[i:i+L] 和 s[j:j+L] 最多 k 个不同。

如何高效实现 check(L)？
方法A：滚动哈希 + 哈希表分组
计算每个起始位置 i 的长度为 L 的子串的哈希值（如多项式哈希），允许最多 k 个不同，意味着如果两个子串哈希值相同，则完全相同（0 不同）；但若不同，可能是由于 k 个字符不同。我们不能直接比较哈希值，因为 k 个不同时哈希值很可能不同。
改进：将子串按某些“特征”分组，比如将子串每隔一定间隔取样本，但实现复杂。

方法B：后缀数组 + 相邻比较
排序后缀后，相邻后缀的公共前缀长度已知。
我们考虑所有起始位置 i，看另一个 j 与 i 的长度为 L 的子串的匹配。
但更有效的是：
对每个连续的排序后缀的区间，如果它们的最长公共前缀 ≥ L - k，那么可能在 L 长度上不超过 k 个不同，但这不是精确的，因为 LCP 是公共前缀长度，超过 LCP 的部分可能全不同。

方法C：动态规划预处理匹配长度
定义 f[i][j] = 从 i 和 j 开始的最长公共前缀的长度（即满足 s[i+t]=s[j+t] 的最大 t）。
计算 f[i][j] 可以用动态规划：
如果 s[i] = s[j]，则 f[i][j] = 1 + f[i+1][j+1]，否则 f[i][j] = 0。
但这样空间 O(n²) 太大。
注意到我们只需要比较长度为 L 的子串，而 f[i][j] 可以在比较过程中逐步计算。

但我们可以用后缀数组的 LCP 来快速得到 f[SA[p]][SA[q]] = min(LCP[p+1..q])。

步骤5：精确的检查算法（利用 LCP 跳过相同部分）

对于固定的 L，我们想找到 i, j 使得从 i 和 j 开始的长度为 L 的子串的不同字符数 ≤ k。
步骤：

  1. 枚举 i 从 0 到 n-L。
  2. 对每个 i，枚举 j 从 i+1 到 n-L。
  3. 比较 s[i:i+L] 和 s[j:j+L] 时，可以用 f[i][j] 跳过相同部分，但 f 未预计算。
    不过，如果我们有后缀数组，可以在比较时利用 LCP 加速，但实现复杂。

实际上常用的是“种子扩展”法：
先比较 s[i] 和 s[j]，如果相同，继续向后，直到不同，记录不同数，如果超过 k 就停止。
但这样在二分时仍可能 O(n³) 最坏。

更优的方法（O(n²) 检查）：
我们并不需要显式比较所有 (i, j)。
用滑动窗口思想：
对每个偏移量 d = j - i > 0，我们比较所有对应的字符对 (p, p+d) 对于 p 从 0 到 n-d-1。
对每个偏移 d，我们可以用双指针扫描：
设数组 diff[p] = (s[p] == s[p+d] ? 0 : 1)。
我们想找长度 L 的窗口，使得窗口内 diff[p] 的和 ≤ k。
即对每个偏移 d，我们在数组 diff 上找长度 L 的滑动窗口，其和 ≤ k。
如果存在这样的窗口，就找到了一对 (i, j) 满足 j-i = d，且子串长度 L 内不同字符数 ≤ k。
对每个 d，我们可以在 O(n) 时间用滑动窗口检查。
总检查时间复杂度：枚举 d 从 1 到 n-1，每个 O(n)，所以 O(n²)。
结合二分长度 L，总 O(n² log n)。

步骤6：算法步骤总结

  1. 二分查找长度 L，范围 [1, n]。
  2. 对每个 L，用步骤5的偏移量法检查：
    • 枚举偏移 d 从 1 到 n-L。
    • 构建数组 diff[p] = (s[p] != s[p+d])?1:0，p 从 0 到 n-d-1。
    • 在 diff 数组上，用长度为 L 的滑动窗口（因为子串长度是 L，窗口内对应 L 个字符比较），计算窗口内 diff 的和。
    • 如果某个窗口和 ≤ k，则 check(L) 返回 true。
  3. 如果 check(L) 为 true，则尝试更大的 L，否则减小 L。
  4. 二分结束后得到最大 L。

步骤7：举例验证

s = "abcabc", k=1。
n=6。
二分 L=3 时：
枚举 d=1:
p: 0 1 2 3 4 5
s[p]: a b c a b c
s[p+d]: b c a b c
diff: 1 1 1 1 1 (长度5)
窗口长度3，最小和=3 > k=1，不满足。
d=2:
s[p]: a b c a b c
s[p+2]: c a b c
diff: 1 1 1 1 (长度4)
窗口和最小=3 >1，不满足。
d=3:
s[p]: a b c a b c
s[p+3]: a b c
diff: 0 0 0 (长度3)
窗口长度3，和=0 ≤1，满足！
所以 L=3 可行。
尝试 L=4：
d=3 时 diff 长度2，窗口长度4 不可能。其他 d 类似，不可行。
所以最大 L=3。

步骤8：复杂度与优化

  • 时间复杂度：二分 O(log n)，每次检查 O(n²)，总 O(n² log n)。
  • 空间复杂度：O(1)，除了存储字符串。

当 n 较大时（如 10⁴），O(n² log n) 可能较慢，但这是允许 k 次不匹配的一般解法。对于 k=0 的精确重复子串，可以用后缀数组+二分在 O(n log n) 解决，但允许 k 次不匹配时，常见做法是这种偏移量法，实践中可通过剪枝优化。

最终答案

这道题结合了二分答案、滑动窗口和字符比较，是“带 k 次不匹配的最长重复子串”的经典线性动态规划思想的延伸应用（虽然主要用滑动窗口检查，但比较过程有动态规划的影子）。核心是通过偏移量将二维比较转为一维数组的滑动窗口和问题，从而在 O(n² log n) 时间内求解。

最长重复子串（后缀数组解法与动态规划结合的变种：带k次不匹配的最长重复子串） 题目描述 给定一个字符串 \( s \) \，和一个整数 \( k \) 。你需要找到最长的重复子串，其中“重复”意味着在字符串中至少出现两次，且这两个出现位置允许最多有 \( k \) 个字符不同（即汉明距离不超过 \( k \) ）。子串可以由任意起始和结束位置定义，但同一个子串在不同位置出现时，只要其对应位置字符不同不超过 \( k \) 次，就算作符合条件的重复子串。求满足条件的最长子串的长度。 示例 输入： s = "abacba" k = 1 输出：3 解释：最长重复子串可以是 "aba"（位置0-2 和 位置2-4，"a b a" 与 "a b a" 距离0，但此处 "aba" 在位置2-4 是 "cba"？实际上需要检查：位置0-2: "aba"，位置3-5: "cba"，距离为2 > k，不满足）。实际上更合适的例子是 "ab" 在位置0-1 和 位置3-4，距离0，长度2，但存在长度3的子串吗？检查 "bac" 在位置1-3 和位置2-4："bac" vs "acb" 距离2 > k，不满足。但如果我们取 "ba" 在位置1-2 和 位置4-5，是 "ba" vs "ba" 距离0，长度2。但输出为3，说明存在长度3的重复子串，比如 "aba" 在位置0-2 和 位置4-6? 但字符串长度为6，没有位置6。所以我们重新看示例： 更清晰的示例： s = "abcabc", k=1 输出可能是3，因为 "abc" 在位置0-2 和位置3-5 完全相同，距离0，长度3。 本题目标：找到最长的子串，使得字符串中存在两个起始位置 i 和 j（i ≠ j），子串 s[ i:i+len] 和 s[ j:j+len ] 最多有 k 个对应字符不同。 解题过程（循序渐进讲解） 步骤1：问题理解与暴力法思路 我们要求的是最长长度 len，使得存在两个起始位置 i, j，满足对于长度 len 的子串，对应字符不同的个数 ≤ k。 暴力法：枚举所有子串长度（从大到小尝试），对每个长度 L，检查是否存在这样的 i, j。 检查方法：枚举所有 i, j，比较 s[ i:i+L] 和 s[ j:j+L ] 的不同字符数是否 ≤ k。 时间复杂度：枚举长度 O(n)，枚举起始位置 O(n²)，比较 O(n)，总 O(n⁴)，太高。 步骤2：基于后缀数组的快速比较 如果知道两个子串的起始位置 i, j，如何快速比较它们长度为 L 的对应字符？ 我们可以用“后缀”的概念：子串 s[ i:i+L ] 是后缀 suffix(i) 的长度为 L 的前缀。 后缀数组（Suffix Array）能将所有后缀排序，并且通过最长公共前缀（LCP）数组，可以快速知道两个后缀的公共前缀长度。 但这里我们需要的是“最多 k 个不同”，而非完全相等，所以 LCP 不能直接解决，但可以帮助减少比较次数。 思路： 构建后缀数组 SA 和 LCP 数组。 对任意两个后缀 suffix(SA[ p]) 和 suffix(SA[ q])，它们的最长公共前缀长度是 min(LCP[ p+1], LCP[ p+2], ..., LCP[ q])（假设 p <q）。 但我们要找的是两个长度固定为 L 的子串，允许 k 个不同。这相当于在排序的后缀中，寻找两个后缀，使得它们的前 L 个字符中，不同字符数 ≤ k。 步骤3：转化为滑动窗口最大值问题 我们固定长度 L，想知道是否存在 i, j 使得子串 s[ i:i+L] 和 s[ j:j+L ] 最多 k 个不同。 换个思路：我们枚举子串的起始位置 i，看是否存在另一个 j 满足条件。但更高效的是用后缀数组： 将所有后缀按字典序排序，那么如果两个后缀的公共前缀很长，它们会在排序后靠近。 对于长度 L 的窗口，我们可以在后缀数组中滑动一个宽度为 w 的窗口，使得窗口内所有后缀的长度为 L 的前缀彼此相差不大，但还是要比较不同字符数。 更好的方法（结合动态规划/预计算）： 定义 diff(i, j) 为 s[ i:i+L] 和 s[ j:j+L ] 的汉明距离。 我们想要 diff(i, j) ≤ k。 预计算 diff 是 O(n²) 的，但我们可以用 DP 思想： diff(i, j) 可以通过前缀和快速计算吗？ 如果定义 same(i, j) = 1 如果 s[ i] = s[ j]，否则 0，那么 diff(i, j) = L - ∑_ {t=0}^{L-1} same(i+t, j+t)。 这需要 O(L) 时间，依然大。 步骤4：二分答案 + 滚动哈希/后缀数组检查 常见技巧：二分查找长度 L。 如果存在长度为 L 的子串满足条件，那么更短的也一定存在（不一定，但我们可以用二分找最大 L）。 检查函数 check(L)：是否存在 i, j 使得 s[ i:i+L] 和 s[ j:j+L ] 最多 k 个不同。 如何高效实现 check(L)？ 方法A：滚动哈希 + 哈希表分组 计算每个起始位置 i 的长度为 L 的子串的哈希值（如多项式哈希），允许最多 k 个不同，意味着如果两个子串哈希值相同，则完全相同（0 不同）；但若不同，可能是由于 k 个字符不同。我们不能直接比较哈希值，因为 k 个不同时哈希值很可能不同。 改进：将子串按某些“特征”分组，比如将子串每隔一定间隔取样本，但实现复杂。 方法B：后缀数组 + 相邻比较 排序后缀后，相邻后缀的公共前缀长度已知。 我们考虑所有起始位置 i，看另一个 j 与 i 的长度为 L 的子串的匹配。 但更有效的是： 对每个连续的排序后缀的区间，如果它们的最长公共前缀 ≥ L - k，那么可能在 L 长度上不超过 k 个不同，但这不是精确的，因为 LCP 是公共前缀长度，超过 LCP 的部分可能全不同。 方法C：动态规划预处理匹配长度 定义 f[ i][ j] = 从 i 和 j 开始的最长公共前缀的长度（即满足 s[ i+t]=s[ j+t ] 的最大 t）。 计算 f[ i][ j ] 可以用动态规划： 如果 s[ i] = s[ j]，则 f[ i][ j] = 1 + f[ i+1][ j+1]，否则 f[ i][ j ] = 0。 但这样空间 O(n²) 太大。 注意到我们只需要比较长度为 L 的子串，而 f[ i][ j ] 可以在比较过程中逐步计算。 但我们可以用后缀数组的 LCP 来快速得到 f[ SA[ p]][ SA[ q]] = min(LCP[ p+1..q ])。 步骤5：精确的检查算法（利用 LCP 跳过相同部分） 对于固定的 L，我们想找到 i, j 使得从 i 和 j 开始的长度为 L 的子串的不同字符数 ≤ k。 步骤： 枚举 i 从 0 到 n-L。 对每个 i，枚举 j 从 i+1 到 n-L。 比较 s[ i:i+L] 和 s[ j:j+L] 时，可以用 f[ i][ j ] 跳过相同部分，但 f 未预计算。 不过，如果我们有后缀数组，可以在比较时利用 LCP 加速，但实现复杂。 实际上常用的是“种子扩展”法： 先比较 s[ i] 和 s[ j ]，如果相同，继续向后，直到不同，记录不同数，如果超过 k 就停止。 但这样在二分时仍可能 O(n³) 最坏。 更优的方法（O(n²) 检查）： 我们并不需要显式比较所有 (i, j)。 用滑动窗口思想： 对每个偏移量 d = j - i > 0，我们比较所有对应的字符对 (p, p+d) 对于 p 从 0 到 n-d-1。 对每个偏移 d，我们可以用双指针扫描： 设数组 diff[ p] = (s[ p] == s[ p+d ] ? 0 : 1)。 我们想找长度 L 的窗口，使得窗口内 diff[ p ] 的和 ≤ k。 即对每个偏移 d，我们在数组 diff 上找长度 L 的滑动窗口，其和 ≤ k。 如果存在这样的窗口，就找到了一对 (i, j) 满足 j-i = d，且子串长度 L 内不同字符数 ≤ k。 对每个 d，我们可以在 O(n) 时间用滑动窗口检查。 总检查时间复杂度：枚举 d 从 1 到 n-1，每个 O(n)，所以 O(n²)。 结合二分长度 L，总 O(n² log n)。 步骤6：算法步骤总结 二分查找长度 L，范围 [ 1, n ]。 对每个 L，用步骤5的偏移量法检查： 枚举偏移 d 从 1 到 n-L。 构建数组 diff[ p] = (s[ p] != s[ p+d ])?1:0，p 从 0 到 n-d-1。 在 diff 数组上，用长度为 L 的滑动窗口（因为子串长度是 L，窗口内对应 L 个字符比较），计算窗口内 diff 的和。 如果某个窗口和 ≤ k，则 check(L) 返回 true。 如果 check(L) 为 true，则尝试更大的 L，否则减小 L。 二分结束后得到最大 L。 步骤7：举例验证 s = "abcabc", k=1。 n=6。 二分 L=3 时： 枚举 d=1: p: 0 1 2 3 4 5 s[ p ]: a b c a b c s[ p+d ]: b c a b c diff: 1 1 1 1 1 (长度5) 窗口长度3，最小和=3 > k=1，不满足。 d=2: s[ p ]: a b c a b c s[ p+2 ]: c a b c diff: 1 1 1 1 (长度4) 窗口和最小=3 >1，不满足。 d=3: s[ p ]: a b c a b c s[ p+3 ]: a b c diff: 0 0 0 (长度3) 窗口长度3，和=0 ≤1，满足！ 所以 L=3 可行。 尝试 L=4： d=3 时 diff 长度2，窗口长度4 不可能。其他 d 类似，不可行。 所以最大 L=3。 步骤8：复杂度与优化 时间复杂度：二分 O(log n)，每次检查 O(n²)，总 O(n² log n)。 空间复杂度：O(1)，除了存储字符串。 当 n 较大时（如 10⁴），O(n² log n) 可能较慢，但这是允许 k 次不匹配的一般解法。对于 k=0 的精确重复子串，可以用后缀数组+二分在 O(n log n) 解决，但允许 k 次不匹配时，常见做法是这种偏移量法，实践中可通过剪枝优化。 最终答案 这道题结合了二分答案、滑动窗口和字符比较，是“带 k 次不匹配的最长重复子串”的经典线性动态规划思想的延伸应用（虽然主要用滑动窗口检查，但比较过程有动态规划的影子）。核心是通过偏移量将二维比较转为一维数组的滑动窗口和问题，从而在 O(n² log n) 时间内求解。