滚动哈希在字符串匹配中的应用：Rabin-Karp算法详解 题目描述 给定一个文本字符串text和一个模式字符串pattern，使用Rabin-Karp算法在text中查找pattern出现的所有起始位置。该算法通过滚动哈希技术，在常数时间内计算文本中滑动窗口的哈希值，从而实现高效的模式匹配。 解题过程 1. 基本思路 Rabin-Karp算法的核心思想是：先计算模式串pattern的哈希值，然后计算文本串text中每个与pattern等长的子串的哈希值。如果某个子串的哈希值与pattern的哈希值相等，则进一步验证该子串是否与pattern完全匹配（防止哈希冲突）。通过滚动哈希技术，可以在O(1)时间内计算下一个子串的哈希值。 2. 哈希函数设计 选择多项式滚动哈希函数，将字符串视为某基数（base）下的数字。例如字符串"abc"可视为： a * base^2 + b * base^1 + c * base^0 。 常用base为131、256等大于字符集大小的质数。 为避免溢出，需对一个大质数（如1e9+7）取模。 3. 计算模式串和第一个窗口的哈希值 设模式串pattern长度为m，文本text长度为n。 计算pattern的哈希值hash_ p。 计算text前m个字符（即第一个窗口）的哈希值hash_ t。 4. 滚动哈希过程 从i=0到n-m遍历文本： 比较当前hash_ t与hash_ p： 若相等，则逐字符比较text[ i..i+m-1 ]与pattern，确认是否匹配。 若匹配，记录起始位置i。 若i < n-m，计算下一个窗口text[ i+1..i+m ]的哈希值： 移除旧字符text[ i]： hash_t = (hash_t - text[i] * base^(m-1)) % mod 添加新字符text[ i+m]： hash_t = (hash_t * base + text[i+m]) % mod 处理负数：若hash_ t为负，加上mod使其非负。 5. 复杂度分析 预处理：计算base的幂次O(m)，哈希值计算O(m)。 匹配：最坏O(nm)（每次哈希匹配都冲突），平均O(n+m)（哈希冲突少）。 6. 关键优化 双哈希：使用两个不同的base和mod计算两组哈希值，仅当两组哈希值均匹配时才进行字符比较，大幅减少冲突概率。 预计算base的幂次：提前计算base^0到base^m，避免重复计算。 示例演示 text = "abracadabra", pattern = "abra" base=131, mod=1e9+7 hash_ p = "abra"的哈希值 初始窗口"abra"哈希值等于hash_ p，匹配成功。 滚动到下一个窗口"brac"：移除'a'，添加'c'，更新哈希值后继续比较。 通过滚动更新，每个窗口的哈希值计算仅需O(1)时间，实现高效匹配。