字符串哈希专题

前言：处理字符串是蓝桥杯国赛经常会用到的，我们这里学习一下字符串哈希

---

下面是一个Python字符串哈希教程，内容涵盖了从基础概念到进阶应用，包括经典的滚动哈希（Rolling Hash），用于字符串匹配（如 Rabin-Karp 算法）和子串比较等常见场景。

---

📘 字符串哈希教程（Python 实现）

🔹 一、什么是字符串哈希？

字符串哈希是一种将一个字符串映射为一个整数的方法，常用于快速比较字符串是否相等。
如果两个字符串的哈希值相等，它们很可能是相等的（有哈希冲突的风险，但通常可以通过双哈希避免）。

---

🔹 二、基础哈希函数

我们使用如下公式将一个字符串 s 转换为哈希值（模拟多项式）：

$$H(s)=s_0\cdot P^0+s_1\cdot P^1+s_2\cdot P^2+\dots +s_{n-1}\cdot P^{n-1}\mathrm{mod}M$$

• P: 一个大于字母表大小的质数（如 31 或 131）
• M: 一个大的模数（如 $10^9+7$）

✅ 示例代码：

def string_hash(s, P=131, M=10**9 + 7):h = 0for ch in s:h = (h * P + ord(ch)) % Mreturn hprint(string_hash("hello"))
print(string_hash("hell"))

---

🔹 三、滚动哈希（Rolling Hash）

滚动哈希常用于子串比较，我们提前计算每个前缀的哈希值，使得任意子串的哈希值可以在 O(1) 时间获得。

✅ 构造哈希前缀数组和 P 的幂数组：

class RollingHash:def __init__(self, s, P=131, M=10**9 + 7):self.s = sself.P = Pself.M = Mn = len(s)self.hash = [0] * (n + 1)self.power = [1] * (n + 1)for i in range(n):self.hash[i + 1] = (self.hash[i] * P + ord(s[i])) % Mself.power[i + 1] = self.power[i] * P % M# 获取 s[l:r] 的哈希值（注意：左闭右开区间）def get_hash(self, l, r):return (self.hash[r] - self.hash[l] * self.power[r - l]) % self.M

这里有一个细节需要处理，就是我们的pow是我们的缩放比例

举个例子，s = “abc”
字符串的哈希值从头开始依次是
a
a * p + b
(a * p+b) * p + c

那么我们计算我们的bc的字符串哈希的值就需要我们用 (a * p+b) * p + c 减去 a * 缩放比例，这里的缩放比例为 p * p

✅ 使用示例：

rh = RollingHash("abracadabra")
print(rh.get_hash(0, 3))  # hash("abr")
print(rh.get_hash(7, 10)) # hash("abr")

当然不难，下面是一些循序渐进的实战题目，从入门到中等难度，帮助你巩固字符串哈希的概念和应用。

---

🧠 字符串哈希实战题目

🌱 入门题目

1. 比较两个子串是否相等（基础）

描述：给定一个字符串 s，和多个查询 (l1, r1, l2, r2)，判断 s[l1:r1] == s[l2:r2] 吗？

输入：

s = "abracadabra"
queries = [(0, 3, 7, 10), (0, 4, 4, 8)]

输出：

True
False

提示：使用滚动哈希 + 子串哈希快速判断是否相等。

---

2. 找出字符串中所有长度为 k 的不同子串个数

描述：给定字符串 s 和整数 k，统计所有长度为 k 的唯一子串个数。

输入：

s = "abcdabc"
k = 3

输出：

5

子串：“abc”, “bcd”, “cda”, “dab”, “abc”（第二个 “abc” 忽略）

---

🌿 进阶题目

3. 最长公共子串（LCS）长度（字符串哈希 + 二分）

描述：给定两个字符串 s1 和 s2，求它们的最长公共子串长度。

思路提示：使用二分长度 + 哈希集合判断是否存在公共子串。

---

4. 是否存在重复的长度为 k 的子串（经典）

描述：给定字符串 s 和整数 k，判断是否存在两个不同位置的长度为 k 的重复子串。

例子：

s = "banana", k = 2
输出: True （"an" 出现了两次）

---

5. 字符串循环等价判定（哈希版）

描述：给定两个字符串 s1 和 s2，判断 s2 是否为 s1 的循环变换（例如 "abc" 的变换包括 "bca" 和 "cab"）。

技巧提示：判断 s2 是否为 s1 + s1 的子串。

---

🚀 挑战题目

6. 最长回文子串长度（哈希 + 二分）

描述：求一个字符串中最长回文子串的长度（可以用 Manacher 或哈希 + 二分实现）。

---