哈希算法题目：基于滚动哈希的高效字符串模式匹配与多模式搜索
字数 3039 2025-12-08 03:49:33

哈希算法题目：基于滚动哈希的高效字符串模式匹配与多模式搜索

题目描述
你需要设计一个字符串搜索系统，该系统能够在给定的主文本字符串 text 中，高效地同时搜索多个模式字符串 patterns 的所有出现位置。假设主文本的长度为 n，模式的总数为 k，所有模式字符串的长度之和为 m。你的目标是返回一个列表，其中每个元素是一个二元组 (pattern_index, start_position)，表示第 pattern_index 个模式在主文本中从 start_position 开始匹配成功。要求算法平均时间复杂度优于朴素的逐个模式、逐字符比较的方法（即优于 O(n * m)），并利用滚动哈希来加速匹配过程。

解题过程循序渐进讲解

步骤1：理解问题与朴素方法的瓶颈
首先明确输入输出：

  • 输入：一个主字符串 text（例如 "abracadabra"），和一个模式字符串列表 patterns（例如 ["abra", "cad", "dab"]）。
  • 输出：所有匹配位置，如 [(0,0), (0,7), (1,4), (2,6)] 表示模式0在位置0和7匹配，模式1在位置4匹配，模式2在位置6匹配。

朴素方法：对每个模式，从主文本的每个起始位置尝试匹配。若模式平均长度为 L，则时间复杂度为 O(n * k * L)，当 k 或 L 较大时效率很低。

目标：利用哈希将每个子串映射为一个整数，通过比较哈希值来快速判断是否可能匹配，从而减少逐字符比较的次数。

步骤2：滚动哈希的基本原理
滚动哈希（Rabin-Karp 思想）允许我们在 O(1) 时间内计算主文本中下一个连续子串的哈希值，前提是已知前一个子串的哈希值。

常用哈希函数形式为多项式哈希：
对于一个字符串 s[0..L-1]，其哈希值 H(s) = (s[0]*p^(L-1) + s[1]*p^(L-2) + ... + s[L-1]*p^0) mod M，其中 p 是一个质数基数（如 31 或 257），M 是一个大质数模数（如 10^9+7）。

滚动计算示例：
已知子串 text[i..i+L-1] 的哈希值 hash1，要计算 text[i+1..i+L] 的哈希值 hash2，公式为：
hash2 = ((hash1 - text[i]*p^(L-1)) * p + text[i+L]) mod M
注意：减法和乘法需在模 M 下进行，且需预先计算 p^(L-1) mod M 备用。

步骤3：扩展到多模式搜索的挑战
不同模式长度可能不同。我们不能用一个固定长度 L 滚动。
解决思路：

  1. 将模式按长度分组，相同长度的模式放在一组。
  2. 对每一组长度 L，我们用滚动哈希计算主文本中所有长度为 L 的子串的哈希值，并与该组所有模式的哈希值比较。

为什么分组？因为滚动哈希要求子串长度固定。
这样，假设有 g 个不同的长度，则我们进行 g 次滚动哈希扫描主文本，每次扫描 O(n) 时间，总复杂度 O(n * g)，再加上哈希比较开销。

步骤4：具体算法步骤
设主文本 text 长度为 n，模式列表 patterns 有 k 个模式。

  1. 预处理模式：

    • 创建一个字典 len_to_patterns，键为模式长度 L，值为列表，存储该长度下的所有模式及其索引。
    • 对每个模式，计算其哈希值（使用与后续滚动哈希相同的 p 和 M），并存入对应长度的列表中。
    • 同时，为防哈希冲突，建议存储模式字符串本身，以便哈希相等时进行最终字符验证。

  2. 滚动哈希扫描主文本：

    • 对 len_to_patterns 中的每个长度 L：
      a. 如果 L > n，跳过（因为主文本中没有足够长的子串）。
      b. 计算主文本前 L 个字符的初始哈希值 hash_text。
      c. 预先计算 p_pow = p^(L-1) mod M 用于滚动。
      d. 创建一个哈希集合 pattern_hashes_set，包含该长度下所有模式的哈希值，并建立哈希值到模式索引的映射（可能多个模式同哈希值，所以映射到列表）。
      e. 从 i = 0 到 n-L：
      - 检查 hash_text 是否在 pattern_hashes_set 中。
      - 如果在，则获取所有对应模式索引，逐个进行逐字符验证（因为哈希可能冲突）。
      - 如果验证通过，记录匹配 (pattern_index, i)。
      - 如果 i < n-L，则滚动更新哈希值：
      hash_text = ((hash_text - ord(text[i])*p_pow) * p + ord(text[i+L])) mod M
      注意取模时避免负数：(hash_text - ord(text[i])*p_pow + M) % M 再计算。

  3. 输出所有匹配记录。

步骤5：复杂度分析

  • 预处理模式：计算每个模式的哈希值，O(m) 时间，m 为模式总长。
  • 滚动扫描：对每个不同长度 L 扫描一次主文本，每次 O(n) 时间。设不同长度数量为 g，则 O(n * g)。
  • 哈希比较与验证：哈希比较 O(1)，验证只在哈希匹配时发生，假设冲突很少，验证总次数 ≈ 匹配次数，可视为 O(匹配数 * 平均模式长度)。

总平均时间复杂度接近 O(m + n * g)，优于朴素 O(n * m) 当 g 较小（即模式长度种类少）。空间复杂度 O(m + k)。

步骤6：举例说明
设 text = "abracadabra", patterns = ["abra", "cad", "dab"]。

  1. 预处理：按长度分组 → 长度4: [("abra", 哈希1, 索引0)], 长度3: [("cad", 哈希2, 索引1), ("dab", 哈希3, 索引2)]。
  2. 对长度4扫描：
    • 计算 text[0..3] 哈希，与 "abra" 哈希比，匹配，验证字符，记录 (0,0)。
    • 滚动到 text[1..4]...
    • 直到 text[7..10] 哈希匹配，验证，记录 (0,7)。
  3. 对长度3扫描：
    • 计算 text[0..2] 哈希，不在集合。
    • 滚动到 text[4..6] 哈希匹配 "cad"，验证，记录 (1,4)。
    • 滚动到 text[6..8] 哈希匹配 "dab"，验证，记录 (2,6)。
  4. 输出：[(0,0), (0,7), (1,4), (2,6)]。

步骤7：进一步优化考虑

  • 如果模式长度种类很多（g 接近 k），可考虑使用后缀自动机或Aho-Corasick 多模式匹配算法，后者能在 O(n + m + 匹配数) 时间内完成，更适合任意长度模式。
  • 滚动哈希中，可使用双哈希（两个不同模数）降低冲突概率。
  • 对于极大文本，可将模式哈希值存入布隆过滤器先行过滤，但需验证。

总结
本题展示了如何利用滚动哈希将多模式匹配问题分解为多个固定长度的单模式匹配（通过哈希比较），从而在模式长度种类较少时获得高效的平均性能。关键在于按长度分组预处理模式，并对每个长度执行一次滚动哈希扫描。这种方法在现实中的文本编辑器搜索、病毒特征码扫描等场景有实用价值。

哈希算法题目：基于滚动哈希的高效字符串模式匹配与多模式搜索 题目描述 你需要设计一个字符串搜索系统，该系统能够在给定的 主文本字符串 text 中，高效地同时搜索 多个模式字符串 patterns 的所有出现位置。假设主文本的长度为 n ，模式的总数为 k ，所有模式字符串的长度之和为 m 。你的目标是返回一个列表，其中每个元素是一个二元组 (pattern_index, start_position) ，表示第 pattern_index 个模式在主文本中从 start_position 开始匹配成功。要求算法平均时间复杂度优于朴素的逐个模式、逐字符比较的方法（即优于 O(n * m)），并利用 滚动哈希 来加速匹配过程。 解题过程循序渐进讲解 步骤1：理解问题与朴素方法的瓶颈 首先明确输入输出： 输入：一个主字符串 text （例如 "abracadabra" ），和一个模式字符串列表 patterns （例如 ["abra", "cad", "dab"] ）。 输出：所有匹配位置，如 [(0,0), (0,7), (1,4), (2,6)] 表示模式0在位置0和7匹配，模式1在位置4匹配，模式2在位置6匹配。 朴素方法 ：对每个模式，从主文本的每个起始位置尝试匹配。若模式平均长度为 L，则时间复杂度为 O(n * k * L)，当 k 或 L 较大时效率很低。 目标 ：利用哈希将每个子串映射为一个整数，通过比较哈希值来快速判断是否可能匹配，从而减少逐字符比较的次数。 步骤2：滚动哈希的基本原理 滚动哈希（Rabin-Karp 思想）允许我们在 O(1) 时间内计算主文本中下一个连续子串的哈希值，前提是已知前一个子串的哈希值。 常用哈希函数形式为多项式哈希： 对于一个字符串 s[0..L-1] ，其哈希值 H(s) = (s[0]*p^(L-1) + s[1]*p^(L-2) + ... + s[L-1]*p^0) mod M ，其中 p 是一个质数基数（如 31 或 257）， M 是一个大质数模数（如 10^9+7）。 滚动计算示例： 已知子串 text[i..i+L-1] 的哈希值 hash1 ，要计算 text[i+1..i+L] 的哈希值 hash2 ，公式为： hash2 = ((hash1 - text[i]*p^(L-1)) * p + text[i+L]) mod M 注意：减法和乘法需在模 M 下进行，且需预先计算 p^(L-1) mod M 备用。 步骤3：扩展到多模式搜索的挑战 不同模式长度可能不同。我们不能用一个固定长度 L 滚动。 解决思路 ： 将模式按长度分组，相同长度的模式放在一组。 对每一组长度 L ，我们用滚动哈希计算主文本中所有长度为 L 的子串的哈希值，并与该组所有模式的哈希值比较。 为什么分组？因为滚动哈希要求子串长度固定。 这样，假设有 g 个不同的长度，则我们进行 g 次滚动哈希扫描主文本，每次扫描 O(n) 时间，总复杂度 O(n * g)，再加上哈希比较开销。 步骤4：具体算法步骤 设主文本 text 长度为 n，模式列表 patterns 有 k 个模式。 预处理模式 ： 创建一个字典 len_to_patterns ，键为模式长度 L，值为列表，存储该长度下的所有模式及其索引。 对每个模式，计算其哈希值（使用与后续滚动哈希相同的 p 和 M），并存入对应长度的列表中。 同时，为防哈希冲突，建议存储模式字符串本身，以便哈希相等时进行最终字符验证。 滚动哈希扫描主文本 ： 对 len_to_patterns 中的每个长度 L： a. 如果 L > n，跳过（因为主文本中没有足够长的子串）。 b. 计算主文本前 L 个字符的初始哈希值 hash_text 。 c. 预先计算 p_pow = p^(L-1) mod M 用于滚动。 d. 创建一个哈希集合 pattern_hashes_set ，包含该长度下所有模式的哈希值，并建立哈希值到模式索引的映射（可能多个模式同哈希值，所以映射到列表）。 e. 从 i = 0 到 n-L： - 检查 hash_text 是否在 pattern_hashes_set 中。 - 如果在，则获取所有对应模式索引，逐个进行逐字符验证（因为哈希可能冲突）。 - 如果验证通过，记录匹配 (pattern_index, i) 。 - 如果 i < n-L，则滚动更新哈希值： hash_text = ((hash_text - ord(text[i])*p_pow) * p + ord(text[i+L])) mod M 注意取模时避免负数： (hash_text - ord(text[i])*p_pow + M) % M 再计算。 输出所有匹配记录 。 步骤5：复杂度分析 预处理模式：计算每个模式的哈希值，O(m) 时间，m 为模式总长。 滚动扫描：对每个不同长度 L 扫描一次主文本，每次 O(n) 时间。设不同长度数量为 g，则 O(n * g)。 哈希比较与验证：哈希比较 O(1)，验证只在哈希匹配时发生，假设冲突很少，验证总次数 ≈ 匹配次数，可视为 O(匹配数 * 平均模式长度)。 总平均时间复杂度接近 O(m + n * g)，优于朴素 O(n * m) 当 g 较小（即模式长度种类少）。空间复杂度 O(m + k)。 步骤6：举例说明 设 text = "abracadabra" , patterns = ["abra", "cad", "dab"] 。 预处理：按长度分组 → 长度4: [ ("abra", 哈希1, 索引0)], 长度3: [ ("cad", 哈希2, 索引1), ("dab", 哈希3, 索引2) ]。 对长度4扫描： 计算 text[ 0..3 ] 哈希，与 "abra" 哈希比，匹配，验证字符，记录 (0,0)。 滚动到 text[ 1..4 ]... 直到 text[ 7..10 ] 哈希匹配，验证，记录 (0,7)。 对长度3扫描： 计算 text[ 0..2 ] 哈希，不在集合。 滚动到 text[ 4..6 ] 哈希匹配 "cad"，验证，记录 (1,4)。 滚动到 text[ 6..8 ] 哈希匹配 "dab"，验证，记录 (2,6)。 输出：[ (0,0), (0,7), (1,4), (2,6) ]。 步骤7：进一步优化考虑 如果模式长度种类很多（g 接近 k），可考虑使用 后缀自动机 或 Aho-Corasick 多模式匹配算法 ，后者能在 O(n + m + 匹配数) 时间内完成，更适合任意长度模式。 滚动哈希中，可使用双哈希（两个不同模数）降低冲突概率。 对于极大文本，可将模式哈希值存入布隆过滤器先行过滤，但需验证。 总结 本题展示了如何利用滚动哈希将多模式匹配问题分解为多个固定长度的单模式匹配（通过哈希比较），从而在模式长度种类较少时获得高效的平均性能。关键在于按长度分组预处理模式，并对每个长度执行一次滚动哈希扫描。这种方法在现实中的文本编辑器搜索、病毒特征码扫描等场景有实用价值。