基于滚动哈希的高效字符串压缩算法（支持重复模式检测与编码）

题目描述
设计一个基于滚动哈希的字符串压缩算法。给定一个字符串 s，算法需要检测其中连续重复出现的子串模式，并将这些重复模式编码为更紧凑的形式。编码格式为：重复子串[重复次数]，其中 重复子串 是最短的重复单元。若子串不重复，则保留原样。
示例：
输入："ababababc"
输出："ab[4]c"（最短重复单元为 "ab"，重复4次，但注意实际子串为 "abababab" 长度为8，由4个 "ab" 组成，末尾的 'c' 单独保留）。
要求：利用滚动哈希（Rabin-Karp 思想）高效检测重复模式，并实现压缩编码。

解题过程

1. 问题理解与核心思路

• 目标：将字符串中连续重复的多个相同子串压缩为“子串[重复次数]”格式，非重复部分原样保留。
• 关键：如何高效找出最短的重复单元？例如 "abababab" 最短单元是 "ab"（长度2），而不是 "abab"（长度4）。
• 滚动哈希作用：快速比较任意子串的哈希值，从而在 O(1) 时间内判断两个子串是否可能相同，避免逐字符比较（仍需最终验证防止哈希冲突）。

2. 滚动哈希原理回顾

• 将字符串视为一个多进制数（例如基数 base=257，取模 mod=2^61-1 避免溢出）。
• 对于字符串 s[0..n-1]，其哈希函数可定义为：
  hash(s[i..j]) = (s[i]*base^(j-i) + s[i+1]*base^(j-i-1) + ... + s[j]) % mod
• 预处理前缀哈希数组 h 和幂数组 p：
  h[i+1] = (h[i] * base + s[i]) % mod
p[i] = base^i % mod
• 则子串 s[l..r] 的哈希值为：
  hash(l, r) = (h[r+1] - h[l] * p[r-l+1] % mod + mod) % mod
• 这样可以在 O(1) 时间内计算任意子串哈希。

3. 算法步骤详解

步骤1：预处理滚动哈希

• 选择基数 base 和模数 mod（通常取大质数，如 10^9+7）。
• 计算字符串 s 的长度 n，初始化 h 和 p 数组。
• 示例：s = "ababababc"，n=9。

步骤2：从左到右扫描，检测重复模式

• 用指针 i 表示当前处理起点。
• 对每个起点 i，尝试寻找从 i 开始的最短重复单元。
• 方法：枚举可能重复单元长度 len 从 1 到 (n-i)/2（因为至少要重复一次）。
  • 用滚动哈希比较 s[i..i+len-1] 与 s[i+len..i+2*len-1] 是否相等（先比哈希，再逐字符验证确保准确）。
  • 若相等，继续检查能否重复更多次：用一个循环，每次向后移动 len 长度，比较后续子串是否与第一个单元相同，直到不同为止，得到重复次数 cnt。
  • 但这样效率不高（O(n^2)）。优化：对每个 i，我们只需要找到能重复至少2次的最短 len。我们可以用哈希值快速判断连续等长子串是否相同。

步骤3：优化重复检测

• 实际不需要枚举所有 len，可以利用“前缀重复”性质：
  • 假设子串 s[i..j] 由 k 个重复单元组成，则单元长度 len 必须能整除 (j-i+1)，且 hash(i, i+len-1) 与 hash(i+len, i+2*len-1) 相同。
• 更高效做法：
  1. 对每个起点 i，计算从 i 开始的最长连续重复串。
  2. 方法：对每个可能的单元长度 len（只需枚举能整除剩余长度的值），用滚动哈希判断后续连续相同。
  3. 但为了总体高效，我们换一种方式：从 i 开始，逐步扩展长度 len，并检查 s[i..i+len-1] 是否能在后面连续重复。
  4. 具体实现时，可以固定 i，让 len 从 1 增加到 (n-i)/2，并维护当前单元 u = s[i..i+len-1] 的哈希值，同时用滚动哈希检查 s[i+len..i+2*len-1] 是否与之相同。若相同，则尝试扩展重复次数。
  5. 记录最大重复次数 maxCnt 及对应的 len。

步骤4：编码与输出

• 若找到重复次数 cnt >= 2，则将 cnt 个重复单元压缩为 单元[重复次数]。
• 指针 i 跳到 i + len*cnt 继续处理。
• 若未找到重复，则直接输出 s[i]，i 加1。

步骤5：举例模拟
以 s = "ababababc" 为例：

• i=0：枚举 len=1，'a' 与 s[1]='b' 不同，跳过。len=2，单元 "ab"，检查 s[2..3]="ab" 相同，继续 s[4..5]="ab" 相同，s[6..7]="ab" 相同，直到 s[8]='c' 不同。共重复 4 次（"abababab" 长度8，含4个单元）。压缩为 "ab[4]"，i 跳到 8。
• i=8：剩余 "c"，无重复，输出 "c"。
• 最终结果："ab[4]c"。

6. 复杂度分析

• 预处理哈希：O(n)。
• 检测重复：对每个起点 i，枚举 len 最坏 O(n)，但实际很多情况可提前终止。
• 利用滚动哈希比较为 O(1)，但需验证防止哈希冲突（概率低）。
• 最坏情况（如全相同字符 "aaaa"）可优化：对每个 i，只需枚举 len 为 (n-i) 的因子，可加速。
• 平均 O(n√n)，但实际滚动哈希大幅减少比较成本。

7. 边界与细节

• 哈希冲突：比较哈希相等后，应再逐字符验证一次确保正确。
• 单元长度：取最短的，例如 "abab" 也可以视为两个 "ab"，应取 "ab"。
• 输出格式：重复次数 cnt 需大于1才压缩。

8. 伪代码

函数 compress(s):
    n = s长度
    预处理哈希数组 h, p
    结果字符串 res = ""
    i = 0
    while i < n:
        bestLen = 1, bestCnt = 1
        for len = 1 to (n-i)/2:
            cnt = 1
            j = i + len
            while j + len <= n 且 哈希相同(i, i+len-1, j, j+len-1) 且 逐字符验证:
                cnt++
                j += len
            if cnt > bestCnt:
                bestCnt = cnt
                bestLen = len
        if bestCnt > 1:
            res += s[i:i+bestLen] + "[" + bestCnt + "]"
            i += bestLen * bestCnt
        else:
            res += s[i]
            i += 1
    return res

这个算法结合滚动哈希快速匹配重复模式，实现了高效的字符串压缩检测。你可以尝试实现并测试不同字符串案例。