哈希算法题目：基于滚动哈希的高效字符串压缩算法（支持重复模式检测与编码）
字数 3240 2025-12-22 14:56:43

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

题目描述
给定一个字符串 s，我们需要设计一个压缩算法，它能检测出 s 中连续重复出现的模式（子串），并将这些重复模式用压缩格式编码。压缩格式定义为：将重复出现的模式用 [重复次数×模式] 表示。例如，字符串 "ababababc" 中模式 "ab" 重复了 4 次，但注意 "abababab" 可以视为 "ab" 重复 4 次，也可以视为 "abab" 重复 2 次。我们要找到一种最优压缩，使得压缩后的字符串长度最短。如果存在多种压缩方式长度相同，选择压缩后字典序最小的表示。要求算法在 O(n²) 时间内完成，并利用滚动哈希加速重复模式的检测。

例如：

  • 输入："ababababc"
    输出："[4×ab]c"（解释："ab" 重复 4 次，最后接 "c"，压缩后长度为 7）
  • 输入："aaa"
    输出："[3×a]"（压缩后长度为 5）
  • 输入："abcabcabcab"
    输出："[4×abc]ab"（"abc" 重复 4 次后余 "ab"，但整体 "abcabcabcab" 可以视为 "[2×abcab]" 吗？注意必须连续重复，这里 "abcab" 不严格重复，所以最优是 "[4×abc]ab"）

解题过程循序渐进讲解

步骤1：理解问题与压缩规则

压缩的目标是：

  1. 找出字符串中连续重复的某个子串 pattern。
  2. 用 [k×pattern] 表示连续 k 次 pattern。
  3. pattern 本身如果还能被压缩，则递归压缩。
  4. 最终使整个字符串压缩后长度最小。

难点：

  • 如何快速判断某个子串是否在后续连续重复？
  • 如何选择 pattern 长度和重复次数？
  • 如何保证整体最优？

步骤2：暴力思路与复杂度

最直接的方法是：

  1. 枚举所有可能的子串起始位置 i 和长度 L，检查从 i 开始是否连续重复多次。
  2. 对每个 pattern 计算压缩后长度，选择最优。
  3. 对 pattern 内部递归压缩。

检查重复需要 O(n) 时间，枚举 O(n²) 个子串，总 O(n³) 会超时。我们需要加速“子串重复检测”。

步骤3：引入滚动哈希加速重复检测

滚动哈希（Rabin-Karp 思想）：

  • 计算字符串的哈希值，使得任意子串的哈希能在 O(1) 时间得到。
  • 哈希函数：H(s[i:j]) = (s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[j-1]) mod M，其中 p 是质数基数，M 是大质数。
  • 预处理前缀哈希，则子串哈希为：
    hash(i, L) = (prefHash[i+L] - prefHash[i] * p^L) mod M
  • 比较两个子串是否相等时，先比哈希值，若相同再逐字符确认（防止哈希冲突）。

这样，判断从 i 开始的长度 L 的子串是否连续重复 k 次，只需比较 hash(i, L)、hash(i+L, L)、hash(i+2L, L)…，每次 O(1)。

步骤4：动态规划定义状态

设 dp[i] 表示子串 s[i:] 压缩后的最短字符串。
最终答案是 dp[0]。

转移方程：

  1. 如果不压缩 s[i]，则 dp[i] = s[i] + dp[i+1]。
  2. 如果从 i 开始，存在长度 L 的子串 pattern 重复 k 次（k ≥ 2），则我们可以压缩为 [k×pattern']，其中 pattern' 是 pattern 压缩后的结果（递归计算）。
    压缩后长度为 len("[k×]") + len(pattern')，其中 len(pattern') 是 pattern 压缩后的长度，即 dp[i][i+L-1] 的结果。

我们需要遍历所有可能的 L（1 到 (n-i)/2），检查最大重复次数 k，然后比较所有方案的压缩后长度。

步骤5：实现重复次数计算

给定 i 和 L，最大重复次数 k 如何快速求？

  • 用滚动哈希，从 i 开始，比较 hash(i, L) 与 hash(i+L, L)、hash(i+2L, L)… 直到不相等。
  • 设重复次数为 cnt，则连续重复 cnt 次相同的 pattern。
  • 但注意，pattern 本身可能还能压缩，所以 pattern 的压缩结果是 compress(s[i:i+L])，这个可以递归用 dp 得到。

我们定义另一个 DP 表 patternDp[l][r] 表示子串 s[l:r+1] 的最短压缩字符串。
这样我们可以用记忆化搜索计算任意子串的压缩结果。

步骤6：算法框架

  1. 预处理滚动哈希所需的前缀哈希数组和 p^L 数组。
  2. 设计函数 compress(l, r) 返回 s[l:r+1] 的最短压缩字符串（记忆化存储）。
  3. 在 compress(l, r) 中：
    • 初始化 best = s[l:r+1]（原串）。
    • 长度 len = r-l+1。
    • 遍历 pattern 长度 L 从 1 到 len/2：
      • 用哈希快速找出从 l 开始，L 长度的 pattern 最大重复次数 cnt。
      • 如果 cnt > 1，则候选压缩字符串为 "[cnt×" + compress(l, l+L-1) + "]"。
      • 如果这个候选长度小于当前 best 长度，更新 best。
      • 如果长度相同，选字典序小的。
    • 返回 best 并存入记忆表。
  4. 最后 compress(0, n-1) 即为答案。

步骤7：举例说明

以 s = "ababababc" 为例：

  1. 计算 compress(0, 8)：
    • 原串长 9。
    • 尝试 L=1，pattern="a"，从位置 0 开始重复次数？"a" 在位置 0,2,4,6 出现，但不是连续重复（中间有 b），所以连续重复次数是 1（不符合 ≥2）。
    • 尝试 L=2，pattern="ab"，从位置 0 开始，计算哈希：hash(0,2)=hash(2,2)=hash(4,2)=hash(6,2) 都相同，连续重复 4 次（位置 0,2,4,6），覆盖长度 8，剩下位置 8 是 "c"。
      • 所以候选为 "[4×" + compress(0,1) + "]c"。
      • compress(0,1) 是 "ab"（不可再压缩）。
      • 候选字符串为 "[4×ab]c"，长度 7。
    • 其他 L 不会更优。
    • 最终 best = "[4×ab]c"。

步骤8：复杂度分析

  • 滚动哈希预处理 O(n)。
  • 状态数 O(n²)，每个状态需要检查 O(n) 个可能的 L，检查重复次数用哈希 O(1) 每次，所以每个状态 O(n) 时间。
  • 总 O(n³)？实际上，检查重复次数时，我们只需要对每个 (l, L) 计算一次重复次数，可以用一个循环提前算出，这样均摊 O(n²) 状态，每个状态 O(n) 时间，总 O(n³)。对于 n 较小（几百）可接受，更大时需进一步优化。

步骤9：进一步优化

注意到我们只需检查 L 使得 cnt*L <= len，且 cnt ≥ 2。
可以在外层循环 L，内层扫一遍字符串，用哈希快速标记重复起始点，这样可以在 O(n²) 内找出所有连续重复段。这是经典“重复子串检测”问题，用滚动哈希 + 最长公共前缀扩展可优化。

但作为基础解法，O(n³) 在 n ≤ 200 时可行，且展示了滚动哈希的核心作用。

步骤10：总结

本题结合了：

  1. 滚动哈希：快速检测重复模式。
  2. 动态规划：选择最优压缩。
  3. 递归记忆化：处理模式内部的压缩。

滚动哈希将子串比较从 O(L) 降到 O(1)，使重复检测可行，是此类“字符串重复模式”问题的关键技术。

哈希算法题目：基于滚动哈希的高效字符串压缩算法（支持重复模式检测与编码） 题目描述 给定一个字符串 s，我们需要设计一个压缩算法，它能检测出 s 中连续重复出现的模式（子串），并将这些重复模式用压缩格式编码。压缩格式定义为：将重复出现的模式用 [重复次数×模式] 表示。例如，字符串 "ababababc" 中模式 "ab" 重复了 4 次，但注意 "abababab" 可以视为 "ab" 重复 4 次，也可以视为 "abab" 重复 2 次。我们要找到一种 最优压缩 ，使得压缩后的字符串长度最短。如果存在多种压缩方式长度相同，选择压缩后字典序最小的表示。要求算法在 O(n²) 时间内完成，并利用滚动哈希加速重复模式的检测。 例如： 输入： "ababababc" 输出： "[4×ab]c" （解释： "ab" 重复 4 次，最后接 "c" ，压缩后长度为 7） 输入： "aaa" 输出： "[3×a]" （压缩后长度为 5） 输入： "abcabcabcab" 输出： "[4×abc]ab" （ "abc" 重复 4 次后余 "ab" ，但整体 "abcabcabcab" 可以视为 "[2×abcab]" 吗？注意必须连续重复，这里 "abcab" 不严格重复，所以最优是 "[4×abc]ab" ） 解题过程循序渐进讲解 步骤1：理解问题与压缩规则 压缩的目标是： 找出字符串中 连续重复 的某个子串 pattern。 用 [k×pattern] 表示连续 k 次 pattern。 pattern 本身如果还能被压缩，则递归压缩。 最终使整个字符串压缩后长度最小。 难点： 如何快速判断某个子串是否在后续连续重复？ 如何选择 pattern 长度和重复次数？ 如何保证整体最优？ 步骤2：暴力思路与复杂度 最直接的方法是： 枚举所有可能的子串起始位置 i 和长度 L，检查从 i 开始是否连续重复多次。 对每个 pattern 计算压缩后长度，选择最优。 对 pattern 内部递归压缩。 检查重复需要 O(n) 时间，枚举 O(n²) 个子串，总 O(n³) 会超时。我们需要加速“子串重复检测”。 步骤3：引入滚动哈希加速重复检测 滚动哈希（Rabin-Karp 思想）： 计算字符串的哈希值，使得任意子串的哈希能在 O(1) 时间得到。 哈希函数： H(s[i:j]) = (s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[j-1]) mod M ，其中 p 是质数基数，M 是大质数。 预处理前缀哈希，则子串哈希为： hash(i, L) = (prefHash[i+L] - prefHash[i] * p^L) mod M 比较两个子串是否相等时，先比哈希值，若相同再逐字符确认（防止哈希冲突）。 这样，判断从 i 开始的长度 L 的子串是否连续重复 k 次，只需比较 hash(i, L) 、 hash(i+L, L) 、 hash(i+2L, L) …，每次 O(1)。 步骤4：动态规划定义状态 设 dp[i] 表示子串 s[i:] 压缩后的最短字符串。 最终答案是 dp[0] 。 转移方程： 如果不压缩 s[i] ，则 dp[i] = s[i] + dp[i+1] 。 如果从 i 开始，存在长度 L 的子串 pattern 重复 k 次（k ≥ 2），则我们可以压缩为 [k×pattern'] ，其中 pattern' 是 pattern 压缩后的结果（递归计算）。 压缩后长度为 len("[k×]") + len(pattern') ，其中 len(pattern') 是 pattern 压缩后的长度，即 dp[i][i+L-1] 的结果。 我们需要遍历所有可能的 L（1 到 (n-i)/2），检查最大重复次数 k，然后比较所有方案的压缩后长度。 步骤5：实现重复次数计算 给定 i 和 L，最大重复次数 k 如何快速求？ 用滚动哈希，从 i 开始，比较 hash(i, L) 与 hash(i+L, L) 、 hash(i+2L, L) … 直到不相等。 设重复次数为 cnt，则连续重复 cnt 次相同的 pattern。 但注意，pattern 本身可能还能压缩，所以 pattern 的压缩结果是 compress(s[i:i+L]) ，这个可以递归用 dp 得到。 我们定义另一个 DP 表 patternDp[l][r] 表示子串 s[ l:r+1 ] 的最短压缩字符串。 这样我们可以用记忆化搜索计算任意子串的压缩结果。 步骤6：算法框架 预处理滚动哈希所需的前缀哈希数组和 p^L 数组。 设计函数 compress(l, r) 返回 s[ l:r+1 ] 的最短压缩字符串（记忆化存储）。 在 compress(l, r) 中： 初始化 best = s[ l:r+1 ]（原串）。 长度 len = r-l+1。 遍历 pattern 长度 L 从 1 到 len/2： 用哈希快速找出从 l 开始，L 长度的 pattern 最大重复次数 cnt。 如果 cnt > 1，则候选压缩字符串为 "[cnt×" + compress(l, l+L-1) + "]" 。 如果这个候选长度小于当前 best 长度，更新 best。 如果长度相同，选字典序小的。 返回 best 并存入记忆表。 最后 compress(0, n-1) 即为答案。 步骤7：举例说明 以 s = "ababababc" 为例： 计算 compress(0, 8) ： 原串长 9。 尝试 L=1，pattern="a"，从位置 0 开始重复次数？ "a" 在位置 0,2,4,6 出现，但不是连续重复（中间有 b），所以连续重复次数是 1（不符合 ≥2）。 尝试 L=2，pattern="ab"，从位置 0 开始，计算哈希： hash(0,2)=hash(2,2)=hash(4,2)=hash(6,2) 都相同，连续重复 4 次（位置 0,2,4,6），覆盖长度 8，剩下位置 8 是 "c"。 所以候选为 "[4×" + compress(0,1) + "]c" 。 compress(0,1) 是 "ab"（不可再压缩）。 候选字符串为 "[4×ab]c" ，长度 7。 其他 L 不会更优。 最终 best = "[4×ab]c" 。 步骤8：复杂度分析 滚动哈希预处理 O(n)。 状态数 O(n²)，每个状态需要检查 O(n) 个可能的 L，检查重复次数用哈希 O(1) 每次，所以每个状态 O(n) 时间。 总 O(n³)？实际上，检查重复次数时，我们只需要对每个 (l, L) 计算一次重复次数，可以用一个循环提前算出，这样均摊 O(n²) 状态，每个状态 O(n) 时间，总 O(n³)。对于 n 较小（几百）可接受，更大时需进一步优化。 步骤9：进一步优化 注意到我们只需检查 L 使得 cnt*L <= len ，且 cnt ≥ 2。 可以在外层循环 L，内层扫一遍字符串，用哈希快速标记重复起始点，这样可以在 O(n²) 内找出所有连续重复段。这是经典“重复子串检测”问题，用滚动哈希 + 最长公共前缀扩展可优化。 但作为基础解法，O(n³) 在 n ≤ 200 时可行，且展示了滚动哈希的核心作用。 步骤10：总结 本题结合了： 滚动哈希 ：快速检测重复模式。 动态规划 ：选择最优压缩。 递归记忆化 ：处理模式内部的压缩。 滚动哈希将子串比较从 O(L) 降到 O(1)，使重复检测可行，是此类“字符串重复模式”问题的关键技术。