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

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

题目描述

设计一个基于滚动哈希的字符串压缩算法。给定一个字符串 s，算法需要检测其中重复出现的子串模式，并将这些重复部分进行编码压缩。压缩格式定义为：当子串 sub 重复出现时，可以用一个标记来表示，例如 sub 在之前某个位置 start 开始、长度为 len，则用 [start,len] 的引用替换重复部分。如果子串未重复，则直接保留原字符。目标是输出一个压缩后的表示形式（或计算压缩比）。

例如：

  • 输入："abcabcabcd"
  • 输出："abc[0,3]d" 或类似表示，表示从位置0开始的长度为3的子串 "abc" 重复出现。
  • 解释：字符串可视为 "abc" 重复两次后再加 "abcd"，但 "abc" 重复出现，因此第二个 "abc" 可以用对第一个 "abc" 的引用代替。

本题要求利用滚动哈希（Rabin-Karp 思想）在 O(n^2) 或更优时间内检测所有可能的重复子串，并选择合适的编码策略。

解题思路

  1. 滚动哈希基础：滚动哈希可以在常数时间内计算任意子串的哈希值，从而快速比较子串是否相等。我们通过预计算字符串的哈希数组和幂数组来实现。
  2. 重复检测：对于每个可能的子串长度 len，从起始位置开始，用哈希表记录已出现子串的起始位置。当发现相同哈希值的子串时，进行逐字符验证以确保不是哈希冲突，然后标记为重复。
  3. 编码选择：为了最大化压缩，应优先选择长且出现次数多的子串进行编码。可采用贪心策略：从长到短检测重复子串，一旦找到可用引用替换的重复块，就进行替换，并重新扫描剩余部分。
  4. 输出压缩表示：将原字符串转换为一个混合序列（直接字符和引用标记），并确保解码时无歧义。

详细解题步骤

步骤1：设计滚动哈希函数

我们采用多项式滚动哈希，选取一个质数基数 base 和一个大质数模数 mod。

  • 定义哈希函数：对于字符串 s，其前缀哈希 hash[i] 表示 s[0:i] 的哈希值。
  • 递推公式：hash[i] = (hash[i-1] * base + s[i-1]) % mod，其中 s[i-1] 是字符的整数值（如 ASCII 码）。
  • 预计算幂数组 power[i] = (power[i-1] * base) % mod，其中 power[0] = 1。
  • 任意子串 s[l:r]（左闭右开）的哈希值为：
    subhash = (hash[r] - hash[l] * power[r-l] % mod + mod) % mod。

这样可以 O(1) 时间得到任意子串哈希。

步骤2：检测所有重复子串

我们按子串长度从大到小扫描（因为长重复子串压缩收益更大），对每个固定长度 len，用哈希表记录子串出现的位置。

  • 外层循环：长度 len 从 n-1 递减到 1（n 为字符串长度）。
  • 内层循环：起始位置 i 从 0 到 n-len，计算子串 s[i:i+len] 的哈希值 h。
  • 用哈希表 map 存储：键为哈希值 h，值为起始位置列表。
  • 当 h 已在表中时，检查对应位置的子串是否确实相等（逐字符比较，防止哈希冲突）。
  • 如果相等，则标记 s[i:i+len] 为重复，并记录其可被引用的位置（例如最早出现的位置）。

注意：为避免重叠替换导致解码困难，我们通常先标记，最后统一选择不重叠的重复块。

步骤3：选择最优编码

目标是找到一组不重叠的重复子串，使得压缩后总长度最小。这是一个区间选择问题，可用贪心或动态规划。

简化贪心策略：

  • 将所有检测到的重复子串按长度降序排序。
  • 依次处理每个重复子串，如果它在当前字符串中未被覆盖（即未被之前的引用替换），则将其替换为引用标记 [start,len]，并标记该区间为已覆盖。
  • 由于我们按长度降序处理，优先选择长的重复子串，通常能得到较好压缩。

步骤4：生成压缩表示

遍历原字符串，根据步骤3得到的替换区间，生成最终输出：

  • 如果当前位置在某个被替换的区间内，则输出引用标记，并跳过整个区间。
  • 否则直接输出当前字符。

引用标记格式可自定义，例如 [start,len] 表示从位置 start 开始长度为 len 的子串。注意：start 是引用子串在原字符串中的起始位置（压缩后可能变化，因此通常引用位置是基于原字符串的，解码时需原字符串）。

示例演示

以 s = "abcabcabcd" 为例：

  1. 计算滚动哈希：

    • 取 base=257, mod=10^9+7。
    • 预计算 hash 和 power 数组。

  2. 检测重复子串：

    • 长度 len=3：子串 "abc" 哈希相同，位置0和3，验证相等，标记为重复。
    • 其他长度可能也有重复，但 len=3 是最长的重复子串。

  3. 选择编码：

    • 重复子串："abc" 出现两次，位置0和3，长度3。
    • 按贪心，选择位置3的 "abc" 替换为引用 [0,3]。

  4. 生成压缩表示：

    • 原字符串：a b c a b c a b c d
    • 位置0-2：直接输出 "abc"。
    • 位置3-5：替换为 "[0,3]"。
    • 位置6-8：直接输出 "abc"（虽然也是 "abc"，但未被标记为替换区间，因为只替换了一处）。
    • 位置9：直接输出 "d"。
    • 结果："abc[0,3]abcd"。

但注意，此结果还可进一步压缩，因为 "abc" 又出现了。我们可以迭代或选择更优区间覆盖。例如，若允许重叠检测，可发现 "abc" 出现三次，将后两次替换为引用，得到 "abc[0,3][0,3]d"。但通常引用标记长度可能超过原串，所以需比较长度。

算法复杂度

  • 滚动哈希预计算：O(n) 时间。
  • 重复检测：对所有长度和起始位置扫描，O(n^2) 时间（但可优化：只检查可能重复的长度，或使用后缀数组/后缀自动机可更优）。
  • 编码选择：取决于重复子串数量，最坏 O(n^2)。
  • 总时间复杂度通常为 O(n^2)，适合中等长度字符串。

关键点

  1. 滚动哈希：快速计算子串哈希，是重复检测的核心。
  2. 哈希冲突处理：当哈希相等时，必须逐字符验证。
  3. 编码策略：简单贪心可能不是全局最优，但通常有效。更优方案可用动态规划寻找最小压缩长度。
  4. 实际应用：此算法思想类似于 LZ77 压缩中的滑动窗口重复引用，滚动哈希加速了匹配查找。

通过以上步骤，你可以实现一个基于滚动哈希的字符串压缩算法，检测重复模式并用引用编码，从而减少字符串的存储或传输长度。

哈希算法题目：基于滚动哈希的高效字符串压缩算法（支持重复模式检测与编码） 题目描述 设计一个基于滚动哈希的字符串压缩算法。给定一个字符串 s ，算法需要检测其中重复出现的子串模式，并将这些重复部分进行编码压缩。压缩格式定义为：当子串 sub 重复出现时，可以用一个标记来表示，例如 sub 在之前某个位置 start 开始、长度为 len ，则用 [start,len] 的引用替换重复部分。如果子串未重复，则直接保留原字符。目标是输出一个压缩后的表示形式（或计算压缩比）。 例如： 输入： "abcabcabcd" 输出： "abc[0,3]d" 或类似表示，表示从位置0开始的长度为3的子串 "abc" 重复出现。 解释：字符串可视为 "abc" 重复两次后再加 "abcd" ，但 "abc" 重复出现，因此第二个 "abc" 可以用对第一个 "abc" 的引用代替。 本题要求利用滚动哈希（Rabin-Karp 思想）在 O(n^2) 或更优时间内检测所有可能的重复子串，并选择合适的编码策略。 解题思路 滚动哈希基础 ：滚动哈希可以在常数时间内计算任意子串的哈希值，从而快速比较子串是否相等。我们通过预计算字符串的哈希数组和幂数组来实现。 重复检测 ：对于每个可能的子串长度 len ，从起始位置开始，用哈希表记录已出现子串的起始位置。当发现相同哈希值的子串时，进行逐字符验证以确保不是哈希冲突，然后标记为重复。 编码选择 ：为了最大化压缩，应优先选择长且出现次数多的子串进行编码。可采用贪心策略：从长到短检测重复子串，一旦找到可用引用替换的重复块，就进行替换，并重新扫描剩余部分。 输出压缩表示 ：将原字符串转换为一个混合序列（直接字符和引用标记），并确保解码时无歧义。 详细解题步骤 步骤1：设计滚动哈希函数 我们采用多项式滚动哈希，选取一个质数基数 base 和一个大质数模数 mod 。 定义哈希函数：对于字符串 s ，其前缀哈希 hash[i] 表示 s[0:i] 的哈希值。 递推公式： hash[i] = (hash[i-1] * base + s[i-1]) % mod ，其中 s[i-1] 是字符的整数值（如 ASCII 码）。 预计算幂数组 power[i] = (power[i-1] * base) % mod ，其中 power[0] = 1 。 任意子串 s[l:r] （左闭右开）的哈希值为： subhash = (hash[r] - hash[l] * power[r-l] % mod + mod) % mod 。 这样可以 O(1) 时间得到任意子串哈希。 步骤2：检测所有重复子串 我们按子串长度从大到小扫描（因为长重复子串压缩收益更大），对每个固定长度 len ，用哈希表记录子串出现的位置。 外层循环：长度 len 从 n-1 递减到 1（ n 为字符串长度）。 内层循环：起始位置 i 从 0 到 n-len ，计算子串 s[i:i+len] 的哈希值 h 。 用哈希表 map 存储：键为哈希值 h ，值为起始位置列表。 当 h 已在表中时，检查对应位置的子串是否确实相等（逐字符比较，防止哈希冲突）。 如果相等，则标记 s[i:i+len] 为重复，并记录其可被引用的位置（例如最早出现的位置）。 注意：为避免重叠替换导致解码困难，我们通常先标记，最后统一选择不重叠的重复块。 步骤3：选择最优编码 目标是找到一组不重叠的重复子串，使得压缩后总长度最小。这是一个区间选择问题，可用贪心或动态规划。 简化贪心策略： 将所有检测到的重复子串按长度降序排序。 依次处理每个重复子串，如果它在当前字符串中未被覆盖（即未被之前的引用替换），则将其替换为引用标记 [start,len] ，并标记该区间为已覆盖。 由于我们按长度降序处理，优先选择长的重复子串，通常能得到较好压缩。 步骤4：生成压缩表示 遍历原字符串，根据步骤3得到的替换区间，生成最终输出： 如果当前位置在某个被替换的区间内，则输出引用标记，并跳过整个区间。 否则直接输出当前字符。 引用标记格式可自定义，例如 [start,len] 表示从位置 start 开始长度为 len 的子串。注意： start 是引用子串在原字符串中的起始位置（压缩后可能变化，因此通常引用位置是基于原字符串的，解码时需原字符串）。 示例演示 以 s = "abcabcabcd" 为例： 计算滚动哈希 ： 取 base=257, mod=10^9+7 。 预计算 hash 和 power 数组。 检测重复子串 ： 长度 len=3 ：子串 "abc" 哈希相同，位置0和3，验证相等，标记为重复。 其他长度可能也有重复，但 len=3 是最长的重复子串。 选择编码 ： 重复子串： "abc" 出现两次，位置0和3，长度3。 按贪心，选择位置3的 "abc" 替换为引用 [0,3] 。 生成压缩表示 ： 原字符串： a b c a b c a b c d 位置0-2：直接输出 "abc" 。 位置3-5：替换为 "[0,3]" 。 位置6-8：直接输出 "abc" （虽然也是 "abc" ，但未被标记为替换区间，因为只替换了一处）。 位置9：直接输出 "d" 。 结果： "abc[0,3]abcd" 。 但注意，此结果还可进一步压缩，因为 "abc" 又出现了。我们可以迭代或选择更优区间覆盖。例如，若允许重叠检测，可发现 "abc" 出现三次，将后两次替换为引用，得到 "abc[0,3][0,3]d" 。但通常引用标记长度可能超过原串，所以需比较长度。 算法复杂度 滚动哈希预计算 ： O(n) 时间。 重复检测 ：对所有长度和起始位置扫描， O(n^2) 时间（但可优化：只检查可能重复的长度，或使用后缀数组/后缀自动机可更优）。 编码选择 ：取决于重复子串数量，最坏 O(n^2) 。 总时间复杂度通常为 O(n^2) ，适合中等长度字符串。 关键点 滚动哈希 ：快速计算子串哈希，是重复检测的核心。 哈希冲突处理 ：当哈希相等时，必须逐字符验证。 编码策略 ：简单贪心可能不是全局最优，但通常有效。更优方案可用动态规划寻找最小压缩长度。 实际应用 ：此算法思想类似于 LZ77 压缩中的滑动窗口重复引用，滚动哈希加速了匹配查找。 通过以上步骤，你可以实现一个基于滚动哈希的字符串压缩算法，检测重复模式并用引用编码，从而减少字符串的存储或传输长度。