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

字数 2458 2025-12-14 01:26:18

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

题目描述
给定一个长字符串 text 和一个模式字符串数组 patterns，需要找出 text 中所有匹配任一 patterns 中模式的子串的起始位置。要求算法在平均情况下具有接近线性时间复杂度，并能处理 patterns 中存在多个模式且总长度可能很大的情况。请设计一个基于滚动哈希的高效算法来解决此问题。

解题过程循序渐进讲解

步骤1：理解问题与挑战
我们要在长字符串 text 中同时查找多个模式串。最直接的方法是逐个模式用朴素匹配（O(n*m)）或KMP（O(n+m)），但若模式很多或总长度大，总时间会很长。我们需要一种能一次性匹配多个模式的方法，滚动哈希（Rabin-Karp的核心思想）可用来快速计算子串哈希，配合哈希集合来同时检查多个模式。

关键思路：

为每个模式计算哈希值，存入哈希集合（或哈希映射，记录对应模式的长度）。
用滚动哈希快速计算 text 中每个与模式等长的子串哈希。
若子串哈希在集合中，再进行逐字符验证（因哈希可能冲突）。
这样平均时间复杂度可接近 O(n + L)，其中 n 是 text 长度，L 是所有模式总长度。

步骤2：滚动哈希设计
滚动哈希需能在常数时间计算下一个子串哈希。常用多项式滚动哈希：

选择基数 base（如 26 对字母，或大素数如 131）和模数 mod（大素数如 10^9+7）。
对字符串 s，哈希为：hash(s) = (s[0]base^{m-1} + s[1]base^{m-2} + ... + s[m-1]) mod mod。
设当前子串 hash H，对应区间 [i, i+m-1]，则下一个子串 [i+1, i+m] 的哈希可滚动计算：
H' = ( (H - s[i]base^{m-1}) base + s[i+m] ) mod mod，注意取模处理负数。

步骤3：预处理模式哈希
遍历 patterns 中每个模式 p：

计算其长度 m 和哈希值 hp（用相同 base 和 mod）。
将 (hp, m) 存入哈希集合（或映射 hp->长度列表，因不同模式可能同哈希）。
注意：模式长度可能不同，需对每个长度单独处理滚动哈希。

步骤4：多长度滚动匹配
因为模式长度不同，需对每个不同长度分别做滚动哈希匹配。

收集所有模式的不同长度值 lengths。
对每个长度 m in lengths：
a. 用滚动哈希计算 text 中所有长度为 m 的子串哈希值。
b. 对每个子串哈希 h，若 h 在集合中（且长度匹配），则取出对应模式列表，逐字符验证是否匹配。
c. 若匹配，记录起始位置。

步骤5：优化与细节

基数与模数选择：为防止哈希冲突过多，可用双哈希（两个不同 mod）进一步降低冲突概率。
哈希集合结构：可用 unordered_map<int, vector<pair<string,int>>>，键为哈希值，值为（模式串，长度）列表，验证时只对比同长度的模式。
滚动计算初始化：对每个长度 m，需先计算 text 的前 m 个字符哈希（O(m)），然后滚动 n-m 次（每次 O(1)）。
边界处理：当 m > n 时跳过。
验证优化：可先快速比较第一个字符，不等则跳过。

步骤6：算法步骤总结
输入：长字符串 text，模式数组 patterns。
输出：所有匹配起始位置列表。

选择基数 base 和模数 mod1（可加 mod2 双哈希）。
构建映射 hash_map：对 patterns 中每个模式 p，计算长度 m 和哈希值 h，将 (p, m) 存入 hash_map[h] 列表。
收集所有模式长度到集合 lengths。
初始化结果列表 matches。
对每个长度 m in lengths：
- 如果 m > text.length()，继续下一长度。
- 计算 text[0..m-1] 的哈希 h0。
- 如果 h0 在 hash_map 中，遍历对应列表，若模式长度等于 m 且 text[0..m-1]==p，记录起始 0。
- 计算 base^{m-1} 的幂 pow_m 备用（预计算避免重复）。
- 循环 i 从 1 到 n-m：
  - 滚动计算哈希：h = ( (h - text[i-1]pow_m) base + text[i+m-1] ) mod mod。
  - 若 h 在 hash_map 中，遍历对应列表，若模式长度等于 m 且 text[i..i+m-1]==p，记录起始 i。
返回 matches。

步骤7：复杂度分析

预处理：计算所有模式哈希 O(L)，L 为模式总长度。
匹配：对每个长度 m，滚动计算哈希 O(n)，每次查哈希表 O(1)，最坏情况每次验证 O(m)（但冲突少时很少发生）。
平均情况接近 O(n + L)。空间复杂度 O(L) 存储模式信息。

步骤8：示例演示
设 text = "abcdecd"，patterns = ["cd", "bcd", "de"]。
base=26, mod=1009。

计算模式哈希：
hash("cd") = (2*26 + 3) mod 1009 = 55?（此处仅为示例，实际按字母序a=0,b=1,...）。
类似得 "bcd" 和 "de"。存入映射。
lengths = {2, 3}。
长度2：计算 text 中所有长2子串哈希，发现 "cd" 在位置2和5匹配。
长度3：滚动计算，发现 "bcd" 在位置1，"dec" 不匹配。
输出匹配位置 [1,2,5]。

最终：此方法利用滚动哈希高效计算子串哈希，配合哈希集合实现多模式一次性匹配，适用于模式多、文本长的场景，是 Rabin-Karp 算法的多模式扩展。

基于滚动哈希的高效字符串模式匹配与多模式搜索题目描述给定一个长字符串 text 和一个模式字符串数组 patterns ，需要找出 text 中所有匹配任一 patterns 中模式的子串的起始位置。要求算法在平均情况下具有接近线性时间复杂度，并能处理 patterns 中存在多个模式且总长度可能很大的情况。请设计一个基于滚动哈希的高效算法来解决此问题。解题过程循序渐进讲解步骤1：理解问题与挑战我们要在长字符串 text 中同时查找多个模式串。最直接的方法是逐个模式用朴素匹配（O(n* m)）或KMP（O(n+m)），但若模式很多或总长度大，总时间会很长。我们需要一种能一次性匹配多个模式的方法，滚动哈希（Rabin-Karp的核心思想）可用来快速计算子串哈希，配合哈希集合来同时检查多个模式。关键思路：为每个模式计算哈希值，存入哈希集合（或哈希映射，记录对应模式的长度）。用滚动哈希快速计算 text 中每个与模式等长的子串哈希。若子串哈希在集合中，再进行逐字符验证（因哈希可能冲突）。这样平均时间复杂度可接近 O(n + L)，其中 n 是 text 长度，L 是所有模式总长度。步骤2：滚动哈希设计滚动哈希需能在常数时间计算下一个子串哈希。常用多项式滚动哈希：选择基数 base （如 26 对字母，或大素数如 131）和模数 mod （大素数如 10^9+7）。对字符串 s，哈希为：hash(s) = (s[ 0] base^{m-1} + s[ 1] base^{m-2} + ... + s[ m-1 ]) mod mod。设当前子串 hash H，对应区间 [ i, i+m-1]，则下一个子串 [ i+1, i+m ] 的哈希可滚动计算： H' = ( (H - s[ i] base^{m-1}) base + s[ i+m ] ) mod mod，注意取模处理负数。步骤3：预处理模式哈希遍历 patterns 中每个模式 p：计算其长度 m 和哈希值 hp（用相同 base 和 mod）。将 (hp, m) 存入哈希集合（或映射 hp->长度列表，因不同模式可能同哈希）。注意：模式长度可能不同，需对每个长度单独处理滚动哈希。步骤4：多长度滚动匹配因为模式长度不同，需对每个不同长度分别做滚动哈希匹配。收集所有模式的不同长度值 lengths。对每个长度 m in lengths： a. 用滚动哈希计算 text 中所有长度为 m 的子串哈希值。 b. 对每个子串哈希 h，若 h 在集合中（且长度匹配），则取出对应模式列表，逐字符验证是否匹配。 c. 若匹配，记录起始位置。步骤5：优化与细节基数与模数选择：为防止哈希冲突过多，可用双哈希（两个不同 mod）进一步降低冲突概率。哈希集合结构：可用 unordered_ map<int, vector<pair <string,int>>>，键为哈希值，值为（模式串，长度）列表，验证时只对比同长度的模式。滚动计算初始化：对每个长度 m，需先计算 text 的前 m 个字符哈希（O(m)），然后滚动 n-m 次（每次 O(1)）。边界处理：当 m > n 时跳过。验证优化：可先快速比较第一个字符，不等则跳过。步骤6：算法步骤总结输入：长字符串 text，模式数组 patterns。输出：所有匹配起始位置列表。选择基数 base 和模数 mod1（可加 mod2 双哈希）。构建映射 hash_ map：对 patterns 中每个模式 p，计算长度 m 和哈希值 h，将 (p, m) 存入 hash_ map[ h ] 列表。收集所有模式长度到集合 lengths。初始化结果列表 matches。对每个长度 m in lengths：如果 m > text.length()，继续下一长度。计算 text[ 0..m-1 ] 的哈希 h0。如果 h0 在 hash_ map 中，遍历对应列表，若模式长度等于 m 且 text[ 0..m-1 ]==p，记录起始 0。计算 base^{m-1} 的幂 pow_ m 备用（预计算避免重复）。循环 i 从 1 到 n-m：滚动计算哈希：h = ( (h - text[ i-1] pow_ m) base + text[ i+m-1 ] ) mod mod。若 h 在 hash_ map 中，遍历对应列表，若模式长度等于 m 且 text[ i..i+m-1 ]==p，记录起始 i。返回 matches。步骤7：复杂度分析预处理：计算所有模式哈希 O(L)，L 为模式总长度。匹配：对每个长度 m，滚动计算哈希 O(n)，每次查哈希表 O(1)，最坏情况每次验证 O(m)（但冲突少时很少发生）。平均情况接近 O(n + L)。空间复杂度 O(L) 存储模式信息。步骤8：示例演示设 text = "abcdecd"，patterns = [ "cd", "bcd", "de" ]。 base=26, mod=1009。计算模式哈希： hash("cd") = (2* 26 + 3) mod 1009 = 55?（此处仅为示例，实际按字母序a=0,b=1,...）。类似得 "bcd" 和 "de"。存入映射。 lengths = {2, 3}。长度2：计算 text 中所有长2子串哈希，发现 "cd" 在位置2和5匹配。长度3：滚动计算，发现 "bcd" 在位置1，"dec" 不匹配。输出匹配位置 [ 1,2,5 ]。最终：此方法利用滚动哈希高效计算子串哈希，配合哈希集合实现多模式一次性匹配，适用于模式多、文本长的场景，是 Rabin-Karp 算法的多模式扩展。