最长重复子串的变种：最多允许k次不匹配的最长重复子串（进阶版：不匹配位置可任意分布，但总不匹配数不超过k） 题目描述 给定一个字符串 s 和一个整数 k。你需要找到 s 中最长的 子串 ，使得这个子串中最多有 k 个位置与它在字符串中 另一个出现位置 对应的字符不同。更形式化地说： 我们要找到两个起始下标 i 和 j（i ≠ j），以及一个长度 L，满足： 子串 s[ i : i+L-1] 和 s[ j : j+L-1 ] 长度均为 L，且这两个子串的对应位置最多有 k 个字符不同。 在所有满足上述条件的 (i, j, L) 中，L 是最大的。 求这个最大的 L。 示例 s = "abcdeabc", k = 1 输出：4 解释：取 i=0（"abcd"），j=4（"eabc"），对应位置逐个比较：a-e（不同）、b-a（不同）、c-b（不同）、d-c（不同）。这里不同字符数为4，不满足 k=1。实际上最长的是长度为4的子串吗？我们看另一对：i=0（"abc"）和 j=5（"abc"），完全匹配，不同数为0，长度为3。但还能更长吗？ 试 i=0（"abcde"）和 j=3（"deabc"）比较：a-d、b-e、c-a、d-b、e-c，全部不同。不是。 实际上，最优是 i=1（"bcde"）和 j=5（"abc"）长度对齐不了。等一下，我们重新理解题意：是找两个起始位置不同的 相同长度 子串，最多允许 k 处不匹配。 例如 s = "abcdeabc", k=1 时，可选 i=0, L=4: "abcd" 和 j=4开始的 "eabc" 比较：a/e, b/a, c/b, d/c 全不同，不满足。 实际上最优是 L=3：i=0的"abc"和j=5的"abc"完全匹配，k=0即可。但题目问最长的 L，也许我们可以允许1处不匹配得到更长的？ 尝试 L=4：所有可能的 i, j 比较，最多相同字符数都不足以让不同字符数 <=1，所以不行。 L=3 是答案。但示例给的是4？那我之前假设示例不对。我们换一个 s="abacab", k=1。 i=0 "abac" 与 j=2 "acab" 比较：a/a(相同), b/c(不同), a/a(相同), c/b(不同)，不同数=2>k。 i=0 "aba" 与 j=3 "cab" 比较：a/c(不同), b/a(不同), a/b(不同)，不同数=3>k。 实际上匹配的 L=2："ab" 与 "ab" 在位置0和3？不对，s[ 3 ]='c'。 其实 s[ 0..1]="ab", s[ 4..5 ]="ab" 匹配，不同数0，L=2。能不能更长？ L=3：s[ 0..2]="aba" 与 s[ 3..5 ]="cab" 不同数=3>1，不行。 所以答案=2。 这说明这个题目并不是简单的“最长重复子串”，而是带k处不匹配的最长近似重复子串。 更直观的例子：s = "abcabc", k=0 时就是最长重复子串（完全匹配），结果是3（"abc"重复一次）。 s = "abcabc", k=1 时，可以考虑 s[ 0..4]="abcab" 与 s[ 1..5 ]="bcabc"，比较长度为5，但不同数=5>1，不行。 实际上 L=3 时完全匹配，L=4 时任何一对都会超过1个不匹配，所以答案=3。 所以题目是： 在字符串 s 中找出两个长度相等且起始位置不同的子串，它们最多有 k 个位置不同，求这两个子串的最大可能长度。 解题思路 这个问题是“带k个不匹配的最长重复子串”，常用解法有两种： 动态规划 + 不匹配计数（O(n²) 时间，适用于小规模字符串） 二分长度 L + 滚动哈希（Robin-Karp）+ 哈希表分组（O(n log n) 时间，适用于较大 n） 这里我们详细讲 动态规划 解法，因为它更直观且是线性DP的一种变体。 动态规划解法步骤 设字符串 s 长度为 n，下标从 0 开始。 1. 状态定义 定义 dp[ i][ j] 表示 以 s[ i] 和 s[ j] 开头的最长匹配长度（允许最多 k 个不匹配） 吗？不，这样不好直接表示，因为“最多k个不匹配”是限制条件，不是一个累积值直接放进状态。 我们换一种状态： 定义 diff[ i][ j] 表示 s[ i] 和 s[ j] 是否不同，即 diff[ i][ j] = 0 如果 s[ i]==s[ j ]，否则 1。 我们想找两个起始位置 a 和 b（a < b），使得从 a 和 b 开始，长度为 L 的子串满足 sum_ {t=0}^{L-1} diff[ a+t][ b+t ] ≤ k，并且 L 最大。 2. 暴力法思路 最直接的方法是枚举所有 a, b（a <b）和长度 L，但这样是 O(n³)。 优化：对于每一对固定的 a, b，我们可以用 滑动窗口 的方法找最大 L，使得窗口内 diff 的和 ≤ k，这是 O(n) 对每个 a,b，总共 O(n³) 依然大。 更好的 DP 思路： 考虑对每个偏移量 d = b-a，比较所有对应位置 (i, i+d) 的字符是否相等。 定义 f[ i ] 表示以 i 和 i+d 为开头的匹配长度内不同字符数不超过k的最大长度？不，还是用前缀和。 3. 动态规划状态设计 我们设 dp[ i][ j] 表示从 i 和 j 开始的 完全匹配的长度 （即从 i 和 j 开始相同字符连续多长），这是经典的最长公共扩展（Longest Common Extension）问题，可以用 DP 反向计算： 如果 s[ i]==s[ j]，则 dp[ i][ j] = 1 + dp[ i+1][ j+1]，否则 dp[ i][ j ]=0。 但这样要 O(n²) 空间，实际上我们可以不用存储所有 i,j，只需在比较时用这个递推，不过我们这里先考虑用这个预处理。 然后，对于每个起点 a, b，我们可以在已知最长公共前缀（LCP）长度 l = dp[ a][ b ] 之后，接着往后比较，但允许跳过不匹配的地方。这其实变成了：在 a+l, b+l 之后允许最多 k 个不匹配的扩展。这仍然不好一次性DP。 4. 改用另一种DP思路 设 g[ i][ j] 表示从 i 和 j 开始，使得 不同字符数不超过k 的最大长度。 那么 g[ i][ j ] 可以递归计算： 如果 s[ i]==s[ j]，则 g[ i][ j] = 1 + g[ i+1][ j+1 ]，但必须保证从 i 到 i+L-1 和 j 到 j+L-1 之间的不同字符数 ≤ k，这个不同字符数在递归过程中累计。 这样需要多一个维度记录已经有多少不同字符数，所以状态是 g[ i][ j][ c ]，c 是当前已用的不匹配次数，表示从 i 和 j 开始，在已用了 c 次不匹配的情况下，还能获得的最大匹配长度。这会导致复杂度 O(n² k)，太大。 实际上我们可以用 二分答案+动态规划验证 来降维。 5. 二分答案+DP验证 二分可能的长度 L（1 到 n）。 检查是否存在 a, b（a<b），使得 s[ a:a+L-1] 和 s[ b:b+L-1 ] 的不同字符数 ≤ k。 如何检查？ 我们可以枚举所有 a, b，比较两个子串的不同字符数，但这是 O(n² L) 太慢。 优化： 设 diff[ a][ b] 表示 s[ a] 与 s[ b ] 是否不同（0/1）。 那么对给定的偏移量 d=b-a，我们看所有 i 从 0 到 n-1-d，子串比较就是比较 s[ i] 与 s[ i+d ] 的相等性序列。 但子串长度是 L，所以从 i 开始长度为 L 的窗口，窗口内对应位置比较的不同字符数 = sum_ {t=0}^{L-1} diff[ i+t][ i+d+t ]。 这是 固定d 的滑动窗口问题：用前缀和可以在 O(n) 内检查某个 d 是否存在某个 i 使不同字符数 ≤ k。 但 d 有 O(n) 种，所以总 O(n²) 检查一个 L，再加上二分 log n，就是 O(n² log n)，对于 n 较大还是高。 但我们用 DP 思路来避免二分？实际上这个问题经典做法是用二分+滚动哈希，但题目要求是线性DP，我们可以用 DP 直接求最大 L。 6. 改用 DP 直接求最大 L 定义 f[ d][ i ] 表示以 i 和 i+d 为起始位置的当前匹配长度内不同字符数。 但我们不存储这个，而是用 f[ d][ i ] 表示从 i 开始，与 i+d 开始，能匹配的最大长度（最多允许k个不匹配）。 这可以这样求： 设 cnt[ d][ i] 表示 s[ i] 与 s[ i+d ] 是否不同，不同则1，同则0。 那么从 i 开始，长度 L 的不同字符数 = cnt[ d][ i] + cnt[ d][ i+1] + ... + cnt[ d][ i+L-1 ]。 我们想找最大的 L 使得这个和 ≤ k。 对每个固定的 d，我们可以用 滑动窗口 找最长的连续段（窗口内和 ≤ k），这是 O(n) 时间。对所有 d 做一次，总 O(n²)。 这个就是最终可行的线性 DP 思路（其实不是 DP，是滑动窗口），但满足“循序渐进讲解”要求，我就把它包装成 DP 递推形式： 设 p[ d][ i ] 表示从 i 开始，在偏移 d 下，从 i 往后的最多不同字符数累计前缀和。 即 p[ d][ i] = p[ d][ i-1] + (s[ i] != s[ i+d]?1:0)，但这里 i 是子串的起始，我们关心的是 i 到 i+L-1 的和，即 p[ d][ i+L-1]-p[ d][ i-1 ] 如果前缀和的话。不过更简单是： 对每个 d，我们枚举 i 从 0 到 n-1-d，维护一个窗口 [ i, i+L-1 ] 使得窗口内和 ≤ k，找最大的 L，这是标准的双指针滑动窗口。 7. 算法步骤 初始化 ans = 0。 枚举偏移量 d 从 1 到 n-1（因为 a <b，所以 b-a = d > 0）： 初始化 left = 0，不同字符数 mismatch = 0。 枚举 right 从 0 到 n-1-d： mismatch 增加 (s[ right] != s[ right+d ] ? 1 : 0)。 当 mismatch > k 时，移动 left 直到 mismatch ≤ k，移动时 mismatch 减少 (s[ left] != s[ left+d ] ? 1 : 0)。 窗口长度 = right - left + 1，用此更新 ans。 输出 ans。 时间复杂度 O(n²)，空间 O(1)。 8. 例子演示 s = "abacab", k=1 n=6 枚举 d=1：比较 s[ i] 与 s[ i+1 ] i=0:a/b 不同=1，窗口[ 0,0 ]长度1，mismatch=1 i=1:b/a 不同+1=2>k，移动 left=1，mismatch 减(s[ 0]!=s[ 1]?1:0)=1，现在 mismatch=1，窗口[ 1,1 ]长度1 i=2:a/c 不同+1=2>k，移动 left=2，mismatch减(s[ 1]!=s[ 2]?1:0)=1，现在 mismatch=1，窗口[ 2,2 ]长度1 i=3:c/a 不同+1=2>k，移动 left=3，mismatch减(s[ 2]!=s[ 3]?1:0)=1，mismatch=1，窗口[ 3,3 ]长度1 i=4:a/b 不同+1=2>k，移动 left=4，mismatch减(s[ 3]!=s[ 4]?1:0)=1，mismatch=1，窗口[ 4,4 ]长度1 i=5:b/越界不比较。 d=1 得到最大长度1。 d=2：比较 s[ i] 与 s[ i+2 ] i=0:a/a 同，mismatch=0，窗口[ 0,0 ]长度1 i=1:b/c 不同+1=1，窗口[ 0,1 ]长度2 i=2:a/a 同，mismatch=1，窗口[ 0,2 ]长度3>k? 不，mismatch=1≤k，长度=3 i=3:c/c? s[ 3]='c', s[ 5]='b' 不同+1=2>k，移动 left 直到 ≤k，最终窗口[ 3,3 ]长度1 ... 最后 d=2 最大长度=3（i=0..2："aba" 与 "aca"，不同只有位置1:b/c 不同1次，满足k=1，长度3） 继续枚举 d=3,4,5 得到最大长度。 最终 ans=3。 9. 总结 这种方法虽然不是传统表格填充的线性DP，但利用了双指针滑动窗口来优化枚举，本质是“对每个偏移量d，求最长子数组使得不同字符数≤k”，这是一个线性时间的扫描，总 O(n²) 时间，O(1) 额外空间。 对于 n 达到几千时可以接受，若 n 更大，需用二分+哈希优化到 O(n log n)。 通过这个解法，我们可以在允许一定不匹配的情况下，找出最长的近似重复子串，应用于DNA序列匹配、文本相似性检测等场景。