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

问题描述

给定一个字符串s，以及一个非负整数k。要求找到s的一个子串，使得这个子串在s中至少出现两次（允许重叠），并且这两个出现位置允许最多k个字符不同（即“不匹配”）。目标是使这样的子串长度最大化。返回这个最大长度。

示例：
输入：s = "ababa", k = 1
输出：4
解释：子串"abab"在s中出现两次（起始位置0和2），允许最多1个字符不同。实际上位置0的"abab"和位置2的"abab"是相同的，没有不匹配，但更长的"ababa"（起始0和2）不匹配字符为位置4的'a'和位置?，但第二个出现结束位置超出范围。仔细计算：以起始位置0和2比较长度为4的子串，"abab"完全相同，长度为4；长度为5的子串"ababa"（起始0）和"aba"（起始2）重叠长度不足5。所以答案是4。

背景知识

• 后缀自动机（Suffix Automaton, SAM）是一种能接受字符串所有后缀的有限状态自动机。它可以在O(n)时间内构建，并包含所有子串的信息。
• 动态规划常用于处理“允许k次不匹配/错误”的限制条件。
• 我们将结合SAM（高效枚举所有子串的出现位置）和DP（计算两个子串的不匹配数）来解决。

解决步骤

步骤1：构建后缀自动机

后缀自动机是一个有向无环图，每个节点（状态）代表一组endpos集合相同的子串。构建算法是线性的，涉及状态转移、后缀链接等。这里简要回顾：

1. 每个状态包含：len（该状态代表的最长子串长度）、link（后缀链接）、next（字符转移）。
2. 从初始状态last = 0开始，逐个添加字符c。
3. 创建新状态cur，len = last.len + 1。
4. 从last开始，如果没有c的转移，则添加转移到cur，并沿后缀链接向上；直到遇到有c转移的状态p或到达初始状态。
5. 如果p没有c转移，将p的c转移设为cur，cur.link = 0。
6. 如果p有c转移q，检查是否len[p] + 1 == len[q]。如果是，cur.link = q；否则复制状态q为clone，更新转移和链接，最后cur.link = clone。
7. 更新last = cur。

构建后，每个状态对应一组子串，这些子串的长度连续，且该状态代表的最长子串长度为len，最短长度为link.len + 1。状态的数量为O(n)。

步骤2：在后缀自动机上动态规划计算不匹配

我们需要对每一对出现位置（i, j），计算它们开始的长度为L的子串的不匹配字符数。但直接枚举所有对是O(n^2)的。利用SAM，我们可以考虑每个状态代表的子串集合：设状态u，其代表的所有子串在s中出现的位置集合（即endpos集合）是已知的（可以在构建时记录）。我们关心的是，从这个集合中任取两个位置p和q（p < q），使得以p和q开始的长度为L的子串的不匹配数不超过k，且L尽可能大。

难点：对于固定的状态u，它对应的子串长度是一个区间[link.len+1, u.len]。对于每个长度L，我们需要检查是否存在两个位置满足条件。我们可以用滑动窗口+动态规划来检查。

核心思路：

• 对每个状态u，获取它的所有出现位置（即endpos集合）。由于子串可能出现多次，我们只关心起始位置。设这些起始位置按顺序排序为pos[0..m-1]。
• 对于一对起始位置p和q（p < q），它们对应的子串是s[p:p+L]和s[q:q+L]。我们需要计算这两个子串的汉明距离（即不匹配字符数）。如果这个距离<=k，则L是一个可行长度。
• 我们想要最大化L，但L受限于u.len（状态u的最长子串长度）。另外，如果L太小，可能不匹配数更少，但我们要找最大L。

处理不匹配数： 计算两个子串的汉明距离可以通过预处理前缀和来快速查询任意子串的不匹配数，但这里子串是随着p,q变化的。注意到如果p和q固定，不匹配数可以这样计算：对于每个偏移t（0<=t<L），比较s[p+t]和s[q+t]。我们可以用动态规划预处理一个数组diff[p][q]表示从p和q开始的最长公共前缀（LCP）长度？但这样是O(n^2)的。优化：使用DP计算不匹配数不超过k的最长长度。

定义DP状态： 设dp[p][q]表示从位置p和q开始，使得不匹配数不超过k的最长长度。但直接二维DP是O(n^2)的。我们需要更高效的方法。

技巧： 对于固定的状态u，其代表的所有子串是相同的字符串（因为它们在SAM的同一个状态中）。但这里允许k次不匹配，所以子串可以不完全相同。我们可以这样考虑：对于状态u，它对应的子串长度至少为min_len = link.len+1，最大为max_len = u.len。我们想知道，是否存在一个长度L（min_len <= L <= max_len），使得存在两个起始位置p,q，子串s[p:p+L]和s[q:q+L]的不匹配数<=k。注意，由于u中的子串是相同的，所以s[p:p+min_len]和s[q:q+min_len]一定是完全相同的（因为它们是u中最短的子串）。那么，不匹配只能出现在扩展的部分（从min_len到L之间）。

因此，我们可以将问题分解：先固定p,q，它们共享一个长度为min_len的公共前缀（完全相同）。然后我们扩展这个公共部分，每次扩展一个字符，如果不匹配则计数+1。我们需要找到最大的扩展长度ext，使得不匹配数<=k，那么总长度L = min_len + ext。

算法步骤：

1. 对每个状态u，收集它的所有出现位置（起始位置）列表poses。这可以在构建SAM时通过DFS或基数排序得到。
2. 对每个状态u，设min_len = link.len + 1, max_len = u.len。
3. 对于poses中的每对位置(p,q)（p<q），计算从p+min_len和q+min_len开始，能扩展多长使得不匹配数<=k。这可以通过双指针（滑动窗口）实现：
   • 令i = p+min_len, j = q+min_len, 不匹配数mismatch = 0, 扩展长度ext = 0。
   • 当i+ext < n 且 j+ext < n 且 mismatch + (s[i+ext] != s[j+ext] ? 1 : 0) <= k 时，如果s[i+ext] != s[j+ext]则mismatch++，ext++。
   • 否则停止。记录扩展长度ext。
   • 注意：扩展长度不能超过max_len - min_len，也不能超过字符串剩余长度。
4. 对于这对(p,q)，可行的长度L = min_len + ext。用这个L更新全局答案ans。
5. 但枚举所有对(p,q)仍然可能太多（最坏O(n^2)）。我们需要进一步优化。

优化： 注意到，当我们固定状态u时，poses中的位置是字符串中所有满足“以该位置开始的长度为min_len的子串相同”的位置。这些位置可能很多。我们可以用滑动窗口在poses上移动，对窗口内的位置对计算扩展长度。但更有效的方法是：对于每个状态u，我们只考虑位置列表中相邻的位置对？因为最长的L可能出现在相邻的位置？不一定，但可以证明，如果我们想要最大长度，只需检查相邻的位置对即可。原因：如果存在两个非相邻位置p<r<q，那么p和q的扩展长度可能小于等于p和r的扩展长度（因为字符串的连续性）。但为了安全，我们检查所有相邻对。

简化： 对于状态u，设位置列表为poses[0..m-1]（递增）。对每个相邻对(poses[i], poses[i+1])，计算扩展长度ext，然后L = min_len + ext。用L更新答案。这样时间复杂度为O(n * 平均相邻对数量)。由于每个位置最多出现在O(n)个状态中，但总状态数为O(n)，每个状态的相邻对数量为O(m)，总时间复杂度可以证明是O(n^2)的？实际上，如果字符串是随机的话，总时间接近O(n^2)，但在最坏情况下（如全相同字符）会退化为O(n^2)。但通常可接受，因为k较小。

计算扩展长度的优化： 我们可以预处理一个数组lcp[i][j]表示从i和j开始的最长公共前缀长度。但这样是O(n^2)的。我们可以用后缀数组+RMQ在O(1)时间内查询任意两个后缀的LCP长度。但这里我们还需要计算不匹配数<=k的最长长度，不完全是LCP。然而，我们可以利用LCP来加速扩展的计算：设从i和j开始的字符串，它们的LCP长度为l。如果l足够长，那么不匹配数可能为0。但因为我们允许k次不匹配，所以我们实际上需要找到最远的位置使得不匹配数<=k。这可以通过双指针在O(L)时间内计算，但L可能很大。替代方法：用动态规划预处理不匹配数的前缀和？不匹配是逐字符比较的，无法快速区间求和。

最终算法（简化版）： 由于k通常不大（比如<=5），我们可以用双指针扫描扩展部分，每次移动右指针直到不匹配数超过k，然后移动左指针。但这里我们只对一个扩展段进行，实际上就是计算从i和j开始的最长前缀使得汉明距离<=k。这可以在O(L)时间内完成，其中L是扩展长度。因为k小，所以平均扩展长度可能不大。

步骤总结：

1. 构建字符串s的后缀自动机。
2. 对每个状态u，通过DFS或拓扑排序获取其所有出现位置（起始位置），存储在列表poses中。注意：一个状态的出现位置可以通过后缀链接树收集所有子状态的位置得到。
3. 对每个状态u：
   • min_len = u.link.len + 1, max_len = u.len。
   • 对poses中每个相邻位置对(p,q)：
     • 计算扩展长度ext = 从p+min_len和q+min_len开始，使得汉明距离<=k的最大长度，且不超过max_len - min_len，也不超过字符串边界。
     • 可行的L = min_len + ext。更新ans = max(ans, L)。
4. 返回ans。

计算扩展长度ext的具体方法：

• 令i = p + min_len, j = q + min_len。
• 用双指针left = 0, right = 0, mismatch = 0。
• 扩展右指针right，每次比较s[i+right]和s[j+right]：
  • 如果s[i+right] != s[j+right]，mismatch++。
  • 如果mismatch > k，则停止扩展，记录当前right为扩展长度。
  • 否则继续right++。
• 但这样得到的是从开始到right-1的子串满足条件。实际上，我们需要的是最长长度，所以应该用滑动窗口维护一个区间使得不匹配数<=k。但这里我们从左到右扫描，一旦mismatch>k就停止，因为我们要找的是从起始开始的最长前缀。这确实是满足条件的最长长度，因为如果跳过某些字符，就不是连续的前缀了。注意：我们允许不匹配发生在任何位置，但必须是连续的前缀。所以这个方法正确。

边界情况： 如果min_len已经满足出现两次（即存在两个位置），那么L至少为min_len。但可能min_len很小，而扩展后更大。如果k=0，那么就退化为寻找最长重复子串（完全相同的两个子串），此时用后缀自动机可以直接得到答案：遍历所有状态，状态的len就是该状态代表的最长子串长度，如果该状态的出现次数>=2，则可以用len更新答案。所以当k=0时，算法应该输出所有状态中满足出现次数>=2的最大len。我们的算法在k=0时，扩展部分必须完全匹配，所以双指针扫描会一直扩展到第一个不匹配处，即LCP长度。所以与标准SAM解法一致。

时间复杂度： 构建SAM O(n)。收集所有位置的复杂度O(n^2)在最坏情况（如全相同字符），但平均情况较好。对于每个状态，检查相邻位置对，总对数量为O(n)（因为每个位置最多出现在O(log n)个状态中？实际上，每个位置会在多个状态中出现，但总位置对数量可能达到O(n^2)）。所以最坏O(n^2)。但k较小时，扩展长度扫描很快。可以进一步优化，例如用后缀数组+二分答案，但实现复杂。

示例演示

以s="ababa", k=1为例：

1. 构建SAM（略）。状态示例：状态1代表子串"a"，出现位置{0,2,4}；状态2代表"ab"，出现位置{0,2}；状态3代表"aba"，出现位置{0,2}；状态4代表"abab"，出现位置{0}? 实际上"abab"只出现一次？检查：s中"abab"从位置0开始，但位置2开始是"aba"，所以只有一次。但状态5代表"b"，出现位置{1,3}等。
2. 考虑状态3：min_len=2（假设link.len=1）, max_len=3。出现位置poses=[0,2]。p=0,q=2。
   • min_len=2，所以前缀"ab"完全匹配。
   • 扩展：i=p+2=2, j=q+2=4。比较s[2]='a'和s[4]='a'，相同，mismatch=0<=1，ext可以+1。但扩展长度不能超过max_len-min_len=1，所以ext=1。
   • L=2+1=3。但"aba"长度3，在位置0和2出现，不匹配数0<=1，所以可行。
3. 考虑状态2：min_len=1, max_len=2。poses=[0,2]。
   • 扩展：i=1,j=3，s[1]='b', s[3]='b'相同，ext=1（不超过1），L=1+1=2。"ab"在位置0和2出现，不匹配0。
4. 考虑状态5：min_len=1, max_len=1。poses=[1,3]。没有扩展，L=1。
5. 但实际答案应该是4，对应子串"abab"？但"abab"在s中只出现一次（位置0），位置2的"aba"不匹配。检查k=1：比较"abab"（位置0）和"aba"（位置2）重叠部分长度为3，不匹配数？我们需要长度4的子串，比较位置0的"abab"和位置2的"abab"（但位置2开始只有3个字符"aba"，所以不能比较长度4）。所以长度4的子串必须起始位置0和1？起始0的"abab"和起始1的"baba"不匹配数2>1。所以答案不是4？但示例说答案是4。重新检查示例：s="ababa", k=1。长度4的子串有哪些？起始0:"abab",起始1:"baba"。是否存在两个起始位置使得子串最多1个不匹配？比较起始0和2的长度4子串：起始0为"abab"，起始2为"aba"（只有3个字符），所以不能比。比较起始0和1：不匹配数2。所以长度4不可能。但答案可能是3？示例说4，可能是笔误。实际上，当k=1时，最长重复子串可以是"aba"（长度3，出现两次，不匹配0）。但如果我们允许不匹配，可以更长？考虑起始0和2的长度4：实际上，从起始0取4个字符"abab"，起始2取4个字符但只有3个字符，所以无法比较4。所以最长可能是3。但题目可能允许子串出现两次时，第二次出现可以截断？题目说“至少出现两次”，通常要求两次出现都是完整的子串。所以示例可能应为3。但为了演示算法，我们继续。

假设我们修改示例为s="ababc", k=1。则"abab"出现？没有。但我们可以用其他例子。

纠正示例： 输入s="ababa", k=0，输出应为3（"aba"）。当k=1时，输出可能为3或4？我们计算一下：长度4的子串，起始0和2，但起始2只有3个字符，所以不能。起始0和1，不匹配2>1。所以长度4不可能。所以答案应为3。但原题示例可能不同。这里我们以算法逻辑为主。

实现细节（伪代码）

class State {
    int len, link;
    map<char,int> next;
    vector<int> poses; // 出现位置（起始位置）
}
构造SAM，并在构建时记录每个状态的endpos集合（通过DFS或基数排序收集所有位置）。

function get_poses(state u):
    // 从后缀链接树DFS收集所有终止位置，并转换为起始位置
    // 每个终止位置pos对应起始位置pos - u.len + 1
    // 但注意：一个状态可能对应多个长度，所以对于每个终止位置，我们需要考虑所有可能的起始位置。
    // 简单方法：在SAM构建时，每个状态记录其第一个出现的位置（或所有终止位置），然后通过后缀链接树合并。
    // 但更准确的是：构建后，对每个状态，我们只知道其代表的所有子串的结束位置集合。我们需要起始位置。
    // 我们可以记录每个状态的所有结束位置，然后对于每个结束位置end，对应的起始位置是end - len + 1 到 end - link.len。
    // 但这样太多。通常我们只关心最长子串的出现位置，即起始位置 = end - u.len + 1。
    // 所以我们记录每个状态的最长子串出现的所有起始位置。

在构建SAM时，每当创建一个新状态cur，设置其first_pos = cur.len - 1（当前字符的索引）。然后通过后缀链接树，将子状态的first_pos合并到父状态。

但这样只能得到最长子串的一个起始位置。要得到所有起始位置，需要在后缀链接树上DFS，收集所有子状态的first_pos，然后去重排序。

然后对每个状态u，poses是已排序的起始位置列表。

主算法：
ans = 0
for 每个状态u:
    min_len = u.link.len + 1
    max_len = u.len
    poses = u.poses
    if poses.size() < 2: continue
    for i in range(0, poses.size()-1):
        p = poses[i], q = poses[i+1]
        // 计算扩展长度
        i1 = p + min_len
        i2 = q + min_len
        ext = 0
        mismatch = 0
        while i1+ext < n and i2+ext < n and ext < max_len - min_len:
            if s[i1+ext] != s2[i2+ext]:
                mismatch += 1
                if mismatch > k: break
            ext += 1
        L = min_len + ext
        ans = max(ans, L)
return ans

注意： 只检查相邻位置对可能不够，因为最优对可能不是相邻的。例如，poses=[0,5,10]，可能最优是0和10。但我们可以检查所有位置对，但那样成本高。一个改进是：对于每个状态，我们可以用滑动窗口维护一个区间，使得区间内任意两个位置的距离不超过某个值？但最坏情况仍需检查所有对。实际上，由于子串相同部分至少为min_len，如果两个位置相距较远，扩展部分可能更容易不匹配。但为简单起见，我们可以检查所有位置对，但限制k很小的情况下，扩展长度可能不会太长，所以检查所有对的代价可能可以接受。当k较大时，复杂度高。

更优方法： 使用后缀数组+高度数组，并结合二分答案和滑动窗口检查，可以在O(n log n)时间内解决。但这里我们聚焦于SAM+DP的思路。

总结

本题结合了后缀自动机（高效处理子串重复出现）和动态规划思想（处理不匹配限制）。通过SAM枚举所有重复子串的候选，然后对每个候选计算在允许k次不匹配下的最大长度。虽然最坏时间复杂度较高，但对于一般字符串和较小k，可以工作。对于大规模数据，需要用后缀数组等更复杂的数据结构优化。