最长重复子串的动态规划解法（允许最多K个字符不同的最长重复子串）
字数 5088 2025-12-15 15:04:39

最长重复子串的动态规划解法（允许最多K个字符不同的最长重复子串）

题目描述

给定一个字符串s，找到其中最长的重复子串。重复子串定义为在s中至少出现两次的子串（允许重叠）。但本题有一个额外限制：允许这两个子串在对应位置上最多有K个字符不同（即最多允许K次不匹配）。求满足条件的最长子串的长度。

示例：
s = "ababa", K = 1
输出: 3
解释: 子串"aba"在索引[0,2]和[2,4]处出现，它们只有索引2和4的字符（a和a）比较时相同，但这里我们比较的是对应位置：位置0-2的"aba"和位置2-4的"aba"。实际上，这两个子串本身是相同的，没有不匹配。但如果我们允许一次不匹配，我们可以找到更长的子串吗？这里最长重复子串是"aba"，长度为3。但注意，如果我们考虑子串"ab"和"ba"（不匹配一次），它们不是相同的子串。题目要求是重复子串，即两个相同的子串，但允许它们比较时最多K个位置不同。更精确的定义是：找到两个起始位置i和j（i≠j），使得从i和j开始、长度为L的子串，对应位置字符不同的个数不超过K，求最大的L。

解题思路

我们可以通过动态规划来解决这个问题。一种常见的方法是使用二维动态规划，但这里我们需要记录两个子串分别从i和j开始，并且允许最多K个不匹配。一个直接的想法是定义dp[i][j]为以s[i]和s[j]结尾的、最多允许K个不匹配的重复子串的长度。但这样定义难以处理不匹配次数。因此，我们可以将问题转化为：对于每一对起始位置(i,j)，找到最长的长度L使得子串s[i:i+L]和s[j:j+L]的汉明距离（不同字符个数）≤K。然后取所有L的最大值。

我们可以通过动态规划计算汉明距离，但更高效的方法是用动态规划记录匹配长度，并单独计数不匹配次数。然而，由于K通常不大，我们可以用一个三维DP：dp[i][j][k]表示以s[i]和s[j]结尾，且恰好有k个不匹配的重复子串的长度。但这样复杂度太高。

另一种思路：定义dp[i][j]为以s[i]和s[j]结尾的、完全相同的重复子串的长度（即不允许不匹配）。这是经典的最长重复子串的动态规划解法（与最长公共子串类似，但i≠j）。然后我们可以尝试扩展，允许不匹配。但允许不匹配时，我们不能简单地用dp[i][j]递推，因为不匹配会中断连续匹配。

为了处理不匹配，我们可以采用以下方法：对于每个固定的偏移量d = j - i（即两个子串起始位置的距离），我们可以在遍历字符串时，维护一个窗口，并记录当前窗口内不匹配的字符数。当不匹配数超过K时，我们调整窗口。这类似于滑动窗口。但我们需要对每个偏移量d都做一次滑动窗口，时间复杂度为O(n^2)，在n较大时可能过高。

但我们可以用动态规划来优化：我们定义f[i][j]为以s[i]和s[j]结尾的子串，在最多允许K个不匹配的情况下，能构成的最长重复子串长度。然而，这个递推关系并不容易直接写出，因为当s[i] != s[j]时，我们需要考虑是否消耗一次不匹配机会，但子串的长度是依赖于前面状态的。

逐步讲解

我们将问题重新定义：寻找两个起始位置i和j（i < j），使得子串s[i:i+L]和s[j:j+L]的对应位置字符不同的个数不超过K，求最大的L。

我们可以用二维动态规划，但状态定义为：dp[i][j]表示以s[i]和s[j]结尾的子串，在最多允许K个不匹配的情况下，能构成的最长公共后缀的长度（注意，这个后缀是重复的，但允许不匹配）。这里的“最长公共后缀”是指，考虑从某个起点开始到i和j结束的子串，但这两个子串不一定从相同的相对位置开始，不过我们只关心以i和j结尾的部分。

实际上，更准确的是：定义dp[i][j]为以s[i]和s[j]结尾的、最多允许K个不匹配的重复子串的长度。但这样，当s[i] == s[j]时，我们可以从dp[i-1][j-1]转移过来，并且不匹配次数不变；当s[i] != s[j]时，我们可以从dp[i-1][j-1]转移过来，但不匹配次数加1。但dp[i][j]需要记录不匹配次数，所以我们用两个状态：dp[i][j]表示长度，另一个数组diff[i][j]表示以i,j结尾的重复子串中的不匹配次数。但这样递推时，diff[i][j]依赖于diff[i-1][j-1]，而当我们从不同的路径过来时，可能产生不同的diff，我们需要保证不匹配次数不超过K。

我们可以定义dp[i][j]为以s[i]和s[j]结尾的、在最多允许K个不匹配的条件下，能构成的最长重复子串的长度。但注意，这个长度是以i和j结尾的，所以子串的结束位置是i和j，起始位置是i-dp[i][j]+1和j-dp[i][j]+1。在递推时，如果s[i] == s[j]，那么dp[i][j] = dp[i-1][j-1] + 1，并且不匹配次数不变；如果s[i] != s[j]，那么如果我们允许一次不匹配，则dp[i][j] = dp[i-1][j-1] + 1，但不匹配次数加1。但如果之前的不匹配次数已经达到K，我们就不能继续了。所以我们需要记录不匹配次数。

因此，我们使用三维动态规划：dp[i][j][k]表示以s[i]和s[j]结尾，且恰好有k个不匹配的最长重复子串的长度。其中k从0到K。

状态转移方程：

  1. 如果s[i] == s[j]：
    dp[i][j][k] = dp[i-1][j-1][k] + 1 （因为当前字符匹配，不匹配次数k不变）
  2. 如果s[i] != s[j]：
    如果k > 0：
    dp[i][j][k] = dp[i-1][j-1][k-1] + 1 （消耗一次不匹配机会）
    否则（k==0）：
    dp[i][j][0] = 0 （因为没有不匹配机会，且当前字符不匹配，所以长度只能为0）

边界条件：
当i==0或j==0时，即字符串的开始，dp[0][j][k]和dp[i][0][k]需要单独处理。实际上，我们可以从1开始索引，并初始化dp[0][:][:] = 0, dp[:][0][:] = 0。

最终答案：所有dp[i][j][k]的最大值，其中i≠j（因为重复子串要求起始位置不同，但这里我们的dp定义已经隐含了i和j是子串的结尾，所以只要dp[i][j][k] > 0，就对应两个以i和j结尾的子串，它们的起始位置分别是i-dp[i][j][k]+1和j-dp[i][j][k]+1，只要这两个起始位置不同，就是合法的重复子串。注意，当i==j时，子串是同一个，我们不认为是重复的，所以我们需要i≠j。但在递推中，i和j可以相等，但这时dp[i][i][k]表示从同一个位置开始的子串，这是没有意义的，所以我们可以在计算答案时排除i==j的情况。

复杂度：O(n^2 * K)，这可能会很高。但我们可以优化，因为K通常很小。

优化

注意到，当K固定时，我们可以在O(n^2)时间内解决。我们可以用二维数组dp[i][j]表示以s[i]和s[j]结尾的、最多允许K个不匹配的最长重复子串的长度，同时用另一个二维数组mismatch[i][j]表示当前子串中不匹配的字符数。但这样递推时，mismatch[i][j]需要从mismatch[i-1][j-1]转移，但当我们遇到不匹配时，mismatch可能增加，而当我们无法增加时（即已达到K），dp[i][j]就不能从dp[i-1][j-1]转移。

实际上，我们可以用以下递推：
设f[i][j]表示以s[i]和s[j]结尾的重复子串的长度，g[i][j]表示这个子串中的不匹配次数。
如果s[i] == s[j]:
f[i][j] = f[i-1][j-1] + 1
g[i][j] = g[i-1][j-1]
否则:
if g[i-1][j-1] < K:
f[i][j] = f[i-1][j-1] + 1
g[i][j] = g[i-1][j-1] + 1
else:
f[i][j] = 0
g[i][j] = 0 // 重置

但这样有问题：当不匹配次数达到K后，我们无法继续扩展，但可能从更短的子串重新开始。例如，如果之前的不匹配次数已经等于K，当前字符又不匹配，那么我们不能扩展，但我们可以从当前位置重新开始一个长度为0的子串（即重置）。但这样，我们可能丢失一些信息，因为有可能从中间某个位置开始一个新的子串，不匹配次数更少。

所以，我们需要在递推时考虑：当无法扩展时，我们可以尝试从前面某个位置重新开始，但这样就不是简单的递推了。

一个更稳健的方法是使用滑动窗口对每个偏移量d进行处理。对于每个d，我们维护一个窗口，用两个指针left和right，并记录当前窗口内不匹配的字符数。当不匹配数超过K时，我们移动左指针。这样，对于每个d，我们可以在O(n)时间内找到最长的子串。由于d有O(n)个，总复杂度O(n^2)。这比三维DP更优。

滑动窗口解法

  1. 枚举偏移量d = j - i，其中1 ≤ d ≤ n-1。固定d后，我们考虑所有i和j满足j = i + d。
  2. 对于固定的d，我们遍历i从0到n-1-d。我们维护一个窗口，初始left = 0，不匹配数count = 0。
  3. 对于每个i，我们比较s[i]和s[i+d]：
    • 如果s[i] == s[i+d]，我们扩展窗口，right = i。
    • 如果s[i] != s[i+d]，我们增加不匹配数count。如果count > K，那么我们需要移动左指针left，直到count ≤ K。移动左指针时，如果s[left] != s[left+d]，则count减1。
  4. 在每一步，当前窗口的长度为(i - left + 1)，更新答案。

注意：窗口内的子串是连续的，即从left到i，对应两个子串s[left:i+1]和s[left+d:i+d+1]，它们的不匹配数不超过K。

这个方法的时间复杂度：枚举d需要O(n)次，每次滑动窗口O(n)，所以总O(n^2)。空间复杂度O(1)。

举例说明

以s = "ababa", K = 1为例。

枚举d=1（即相邻字符比较）：
i=0: s[0]='a', s[1]='b', 不匹配，count=1 ≤ K, 窗口[0,0], 长度=1。
i=1: s[1]='b', s[2]='a', 不匹配，此时count变为2 > K，所以移动左指针：left=0, s[0]≠s[1], 所以count减为1。左指针移动到1。窗口[1,1], 长度=1。
i=2: s[2]='a', s[3]='b', 不匹配，count=2 > K, 移动左指针：left=1, s[1]≠s[2], count减为1。左指针移动到2。窗口[2,2], 长度=1。
i=3: s[3]='b', s[4]='a', 不匹配，count=2 > K, 移动左指针：left=2, s[2]≠s[3], count减为1。左指针移动到3。窗口[3,3], 长度=1。
此时最大长度为1。

枚举d=2：
i=0: s[0]='a', s[2]='a', 匹配，count=0, 窗口[0,0], 长度=1。
i=1: s[1]='b', s[3]='b', 匹配，count=0, 窗口[0,1], 长度=2。
i=2: s[2]='a', s[4]='a', 匹配，count=0, 窗口[0,2], 长度=3。此时最大长度为3。

枚举d=3,4得到的长度更小。所以最终答案是3。

总结

这个问题可以通过枚举偏移量并使用滑动窗口在O(n^2)时间内解决，其中n是字符串长度。对于每个偏移量，我们维护一个窗口，使得窗口内两个子串的不匹配字符数不超过K，并记录最大窗口长度。最终取所有偏移量中的最大值作为答案。这种方法避免了复杂的三维DP，更高效且易于实现。

最长重复子串的动态规划解法（允许最多K个字符不同的最长重复子串） 题目描述 给定一个字符串s，找到其中最长的重复子串。重复子串定义为在s中至少出现两次的子串（允许重叠）。但本题有一个额外限制：允许这两个子串在对应位置上最多有K个字符不同（即最多允许K次不匹配）。求满足条件的最长子串的长度。 示例： s = "ababa", K = 1 输出: 3 解释: 子串"aba"在索引[ 0,2]和[ 2,4 ]处出现，它们只有索引2和4的字符（a和a）比较时相同，但这里我们比较的是对应位置：位置0-2的"aba"和位置2-4的"aba"。实际上，这两个子串本身是相同的，没有不匹配。但如果我们允许一次不匹配，我们可以找到更长的子串吗？这里最长重复子串是"aba"，长度为3。但注意，如果我们考虑子串"ab"和"ba"（不匹配一次），它们不是相同的子串。题目要求是重复子串，即两个相同的子串，但允许它们比较时最多K个位置不同。更精确的定义是：找到两个起始位置i和j（i≠j），使得从i和j开始、长度为L的子串，对应位置字符不同的个数不超过K，求最大的L。 解题思路 我们可以通过动态规划来解决这个问题。一种常见的方法是使用二维动态规划，但这里我们需要记录两个子串分别从i和j开始，并且允许最多K个不匹配。一个直接的想法是定义dp[ i][ j]为以s[ i]和s[ j]结尾的、最多允许K个不匹配的重复子串的长度。但这样定义难以处理不匹配次数。因此，我们可以将问题转化为：对于每一对起始位置(i,j)，找到最长的长度L使得子串s[ i:i+L]和s[ j:j+L ]的汉明距离（不同字符个数）≤K。然后取所有L的最大值。 我们可以通过动态规划计算汉明距离，但更高效的方法是用动态规划记录匹配长度，并单独计数不匹配次数。然而，由于K通常不大，我们可以用一个三维DP：dp[ i][ j][ k]表示以s[ i]和s[ j ]结尾，且恰好有k个不匹配的重复子串的长度。但这样复杂度太高。 另一种思路：定义dp[ i][ j]为以s[ i]和s[ j]结尾的、完全相同的重复子串的长度（即不允许不匹配）。这是经典的最长重复子串的动态规划解法（与最长公共子串类似，但i≠j）。然后我们可以尝试扩展，允许不匹配。但允许不匹配时，我们不能简单地用dp[ i][ j ]递推，因为不匹配会中断连续匹配。 为了处理不匹配，我们可以采用以下方法：对于每个固定的偏移量d = j - i（即两个子串起始位置的距离），我们可以在遍历字符串时，维护一个窗口，并记录当前窗口内不匹配的字符数。当不匹配数超过K时，我们调整窗口。这类似于滑动窗口。但我们需要对每个偏移量d都做一次滑动窗口，时间复杂度为O(n^2)，在n较大时可能过高。 但我们可以用动态规划来优化：我们定义f[ i][ j]为以s[ i]和s[ j]结尾的子串，在最多允许K个不匹配的情况下，能构成的最长重复子串长度。然而，这个递推关系并不容易直接写出，因为当s[ i] != s[ j ]时，我们需要考虑是否消耗一次不匹配机会，但子串的长度是依赖于前面状态的。 逐步讲解 我们将问题重新定义：寻找两个起始位置i和j（i < j），使得子串s[ i:i+L]和s[ j:j+L ]的对应位置字符不同的个数不超过K，求最大的L。 我们可以用二维动态规划，但状态定义为：dp[ i][ j]表示以s[ i]和s[ j ]结尾的子串，在最多允许K个不匹配的情况下，能构成的最长公共后缀的长度（注意，这个后缀是重复的，但允许不匹配）。这里的“最长公共后缀”是指，考虑从某个起点开始到i和j结束的子串，但这两个子串不一定从相同的相对位置开始，不过我们只关心以i和j结尾的部分。 实际上，更准确的是：定义dp[ i][ j]为以s[ i]和s[ j]结尾的、最多允许K个不匹配的重复子串的长度。但这样，当s[ i] == s[ j]时，我们可以从dp[ i-1][ j-1]转移过来，并且不匹配次数不变；当s[ i] != s[ j]时，我们可以从dp[ i-1][ j-1]转移过来，但不匹配次数加1。但dp[ i][ j]需要记录不匹配次数，所以我们用两个状态：dp[ i][ j]表示长度，另一个数组diff[ i][ j]表示以i,j结尾的重复子串中的不匹配次数。但这样递推时，diff[ i][ j]依赖于diff[ i-1][ j-1 ]，而当我们从不同的路径过来时，可能产生不同的diff，我们需要保证不匹配次数不超过K。 我们可以定义dp[ i][ j]为以s[ i]和s[ j]结尾的、在最多允许K个不匹配的条件下，能构成的最长重复子串的长度。但注意，这个长度是以i和j结尾的，所以子串的结束位置是i和j，起始位置是i-dp[ i][ j]+1和j-dp[ i][ j]+1。在递推时，如果s[ i] == s[ j]，那么dp[ i][ j] = dp[ i-1][ j-1] + 1，并且不匹配次数不变；如果s[ i] != s[ j]，那么如果我们允许一次不匹配，则dp[ i][ j] = dp[ i-1][ j-1 ] + 1，但不匹配次数加1。但如果之前的不匹配次数已经达到K，我们就不能继续了。所以我们需要记录不匹配次数。 因此，我们使用三维动态规划：dp[ i][ j][ k]表示以s[ i]和s[ j ]结尾，且恰好有k个不匹配的最长重复子串的长度。其中k从0到K。 状态转移方程： 如果s[ i] == s[ j ]： dp[ i][ j][ k] = dp[ i-1][ j-1][ k ] + 1 （因为当前字符匹配，不匹配次数k不变） 如果s[ i] != s[ j ]： 如果k > 0： dp[ i][ j][ k] = dp[ i-1][ j-1][ k-1 ] + 1 （消耗一次不匹配机会） 否则（k==0）： dp[ i][ j][ 0 ] = 0 （因为没有不匹配机会，且当前字符不匹配，所以长度只能为0） 边界条件： 当i==0或j==0时，即字符串的开始，dp[ 0][ j][ k]和dp[ i][ 0][ k]需要单独处理。实际上，我们可以从1开始索引，并初始化dp[ 0][ :][ :] = 0, dp[ :][ 0][ : ] = 0。 最终答案：所有dp[ i][ j][ k]的最大值，其中i≠j（因为重复子串要求起始位置不同，但这里我们的dp定义已经隐含了i和j是子串的结尾，所以只要dp[ i][ j][ k] > 0，就对应两个以i和j结尾的子串，它们的起始位置分别是i-dp[ i][ j][ k]+1和j-dp[ i][ j][ k]+1，只要这两个起始位置不同，就是合法的重复子串。注意，当i==j时，子串是同一个，我们不认为是重复的，所以我们需要i≠j。但在递推中，i和j可以相等，但这时dp[ i][ i][ k ]表示从同一个位置开始的子串，这是没有意义的，所以我们可以在计算答案时排除i==j的情况。 复杂度：O(n^2 * K)，这可能会很高。但我们可以优化，因为K通常很小。 优化 注意到，当K固定时，我们可以在O(n^2)时间内解决。我们可以用二维数组dp[ i][ j]表示以s[ i]和s[ j]结尾的、最多允许K个不匹配的最长重复子串的长度，同时用另一个二维数组mismatch[ i][ j]表示当前子串中不匹配的字符数。但这样递推时，mismatch[ i][ j]需要从mismatch[ i-1][ j-1]转移，但当我们遇到不匹配时，mismatch可能增加，而当我们无法增加时（即已达到K），dp[ i][ j]就不能从dp[ i-1][ j-1 ]转移。 实际上，我们可以用以下递推： 设f[ i][ j]表示以s[ i]和s[ j]结尾的重复子串的长度，g[ i][ j ]表示这个子串中的不匹配次数。 如果s[ i] == s[ j ]: f[ i][ j] = f[ i-1][ j-1 ] + 1 g[ i][ j] = g[ i-1][ j-1 ] 否则: if g[ i-1][ j-1] < K: f[ i][ j] = f[ i-1][ j-1 ] + 1 g[ i][ j] = g[ i-1][ j-1 ] + 1 else: f[ i][ j ] = 0 g[ i][ j ] = 0 // 重置 但这样有问题：当不匹配次数达到K后，我们无法继续扩展，但可能从更短的子串重新开始。例如，如果之前的不匹配次数已经等于K，当前字符又不匹配，那么我们不能扩展，但我们可以从当前位置重新开始一个长度为0的子串（即重置）。但这样，我们可能丢失一些信息，因为有可能从中间某个位置开始一个新的子串，不匹配次数更少。 所以，我们需要在递推时考虑：当无法扩展时，我们可以尝试从前面某个位置重新开始，但这样就不是简单的递推了。 一个更稳健的方法是使用滑动窗口对每个偏移量d进行处理。对于每个d，我们维护一个窗口，用两个指针left和right，并记录当前窗口内不匹配的字符数。当不匹配数超过K时，我们移动左指针。这样，对于每个d，我们可以在O(n)时间内找到最长的子串。由于d有O(n)个，总复杂度O(n^2)。这比三维DP更优。 滑动窗口解法 枚举偏移量d = j - i，其中1 ≤ d ≤ n-1。固定d后，我们考虑所有i和j满足j = i + d。 对于固定的d，我们遍历i从0到n-1-d。我们维护一个窗口，初始left = 0，不匹配数count = 0。 对于每个i，我们比较s[ i]和s[ i+d ]： 如果s[ i] == s[ i+d ]，我们扩展窗口，right = i。 如果s[ i] != s[ i+d]，我们增加不匹配数count。如果count > K，那么我们需要移动左指针left，直到count ≤ K。移动左指针时，如果s[ left] != s[ left+d ]，则count减1。 在每一步，当前窗口的长度为(i - left + 1)，更新答案。 注意：窗口内的子串是连续的，即从left到i，对应两个子串s[ left:i+1]和s[ left+d:i+d+1 ]，它们的不匹配数不超过K。 这个方法的时间复杂度：枚举d需要O(n)次，每次滑动窗口O(n)，所以总O(n^2)。空间复杂度O(1)。 举例说明 以s = "ababa", K = 1为例。 枚举d=1（即相邻字符比较）： i=0: s[ 0]='a', s[ 1]='b', 不匹配，count=1 ≤ K, 窗口[ 0,0 ], 长度=1。 i=1: s[ 1]='b', s[ 2]='a', 不匹配，此时count变为2 > K，所以移动左指针：left=0, s[ 0]≠s[ 1], 所以count减为1。左指针移动到1。窗口[ 1,1 ], 长度=1。 i=2: s[ 2]='a', s[ 3]='b', 不匹配，count=2 > K, 移动左指针：left=1, s[ 1]≠s[ 2], count减为1。左指针移动到2。窗口[ 2,2 ], 长度=1。 i=3: s[ 3]='b', s[ 4]='a', 不匹配，count=2 > K, 移动左指针：left=2, s[ 2]≠s[ 3], count减为1。左指针移动到3。窗口[ 3,3 ], 长度=1。 此时最大长度为1。 枚举d=2： i=0: s[ 0]='a', s[ 2]='a', 匹配，count=0, 窗口[ 0,0 ], 长度=1。 i=1: s[ 1]='b', s[ 3]='b', 匹配，count=0, 窗口[ 0,1 ], 长度=2。 i=2: s[ 2]='a', s[ 4]='a', 匹配，count=0, 窗口[ 0,2 ], 长度=3。此时最大长度为3。 枚举d=3,4得到的长度更小。所以最终答案是3。 总结 这个问题可以通过枚举偏移量并使用滑动窗口在O(n^2)时间内解决，其中n是字符串长度。对于每个偏移量，我们维护一个窗口，使得窗口内两个子串的不匹配字符数不超过K，并记录最大窗口长度。最终取所有偏移量中的最大值作为答案。这种方法避免了复杂的三维DP，更高效且易于实现。