字符串哈希算法详解：原理、实现与应用

字符串哈希是一种高效处理字符串匹配和比较的技术，它通过将字符串映射为一个唯一的数值（哈希值），从而在O(1)时间内完成子串的比较。本文将结合代码实现，详细讲解前缀哈希法的工作原理，并通过流程图逐步解析其执行过程。

---

. 字符串哈希的核心思想

字符串哈希的核心目标是：

• 将任意长度的字符串转换为固定大小的哈希值。

• 支持快速比较两个子串是否相同（时间复杂度O(1)）。

• 适用于大规模文本处理（如DNA序列比对、 plagiarism检测等）。

1.1 哈希函数设计

常用的字符串哈希方法是多项式滚动哈希（Polynomial Rolling Hash），其公式为：

H(S)=(S[0]×Pn−1+S[1]×Pn−2+⋯+S[n−1]×P0)mod  MH(S)=(S[0]×Pn−1+S[1]×Pn−2+⋯+S[n−1]×P0)modM

其中：

• PP 是一个质数（通常取131或13331）。

• MM 是一个大数（如 264264，代码中用 unsigned long long 自然溢出替代取模）。

---

2. 代码实现解析

以下是基于前缀哈希的字符串匹配代码（支持快速比较任意两个子串）：

2.1 变量定义

#include <stdio.h>
#include <string.h>#define N 100010
#define P 131  // 经验值，减少冲突typedef unsigned long long Ull;Ull h[N];  // h[i]存储前i个字符的哈希值
Ull p[N];  // p[i]存储P的i次幂

2.2 初始化哈希数组

int main() {int n, m;char str[N];scanf("%d%d", &n, &m);scanf("%s", str + 1);  // 从str[1]开始存储p[0] = 1;for (int i = 1; i <= n; i++) {p[i] = p[i - 1] * P;           // 计算P^ih[i] = h[i - 1] * P + str[i];  // 计算前i个字符的哈希值}// ...后续处理查询
}

初始化过程详解

1. p[i] = P^i：预计算幂次，用于后续子串哈希计算。

2. h[i] = h[i-1] * P + str[i]：递推计算前缀哈希值。

示例（假设 str = "ABC"，P=131）：

• h[0] = 0

• h[1] = h[0]*131 + 'A' = 65

• h[2] = h[1]*131 + 'B' = 65*131 + 66 = 8581

• h[3] = h[2]*131 + 'C' = 8581*131 + 67 = 1123988

---

2.3 子串哈希计算

Ull get(int l, int r) {return h[r] - h[l - 1] * p[r - l + 1];
}

公式解析

H(S[l..r])=H(r)−H(l−1)×Pr−l+1H(S[l..r])=H(r)−H(l−1)×Pr−l+1

• h[r]：前 r 个字符的哈希值。

• h[l-1] * p[r-l+1]：前 l-1 个字符的哈希值左移到对齐位置。

示例（计算 "BC" 在 "ABC" 中的哈希值）：

• get(2, 3) = h[3] - h[1]*p[2] = 1123988 - 65*17161 = 1123988 - 1115465 = 8523

---

2.4 查询处理

while (m--) {int l1, r1, l2, r2;scanf("%d%d%d%d", &l1, &r1, &l2, &r2);if (get(l1, r1) == get(l2, r2))printf("Yes\n");elseprintf("No\n");
}

能：比较两个子串 str[l1..r1] 和 str[l2..r2] 是否相同。

---

3. 流程图详解

以下是代码执行的流程图：

graph TDA[开始] --> B[输入n,m和字符串str]B --> C[初始化p[0]=1, h[0]=0]C --> D[循环i=1到n]D --> E[计算p[i] = p[i-1] * P]E --> F[计算h[i] = h[i-1] * P + str[i]]F --> DD --> G[输入查询次数m]G --> H[循环m次]H --> I[输入l1,r1,l2,r2]I --> J[计算Hash1=get(l1,r1)]I --> K[计算Hash2=get(l2,r2)]J --> L{Hash1 == Hash2?}K --> LL --> |Yes| M[输出"Yes"]L --> |No| N[输出"No"]M --> HN --> HH --> O[结束]

4. 关键问题解答

4.1 为什么选择P=131？

• 131是一个经验值，满足：

  • 足够大以减少冲突。

  • 是质数，保证哈希分布均匀。

• 其他常见选择：13331、99991等。

4.2 如何处理哈希冲突？

• 理论上，unsigned long long 自然溢出相当于模 264264，冲突概率极低。

• 如果需绝对准确，可双哈希（用两个不同的P计算）。

4.3 时间复杂度分析

操作	时间复杂度
初始化哈希数组	O(n)
单次子串比较	O(1)
m次查询	O(m)

5. 应用场景

1. 快速子串匹配（如Rabin-Karp算法）。

2. 最长回文子串（结合二分搜索）。

3. 文本去重（比较哈希值而非原始字符串）。

---

6. 完整代码

#include <stdio.h>
#include <string.h>#define N 100010
#define P 131typedef unsigned long long Ull;Ull h[N], p[N];Ull get(int l, int r) {return h[r] - h[l - 1] * p[r - l + 1];
}int main() {int n, m;char str[N];scanf("%d%d", &n, &m);scanf("%s", str + 1);p[0] = 1;for (int i = 1; i <= n; i++) {p[i] = p[i - 1] * P;h[i] = h[i - 1] * P + str[i];}while (m--) {int l1, r1, l2, r2;scanf("%d%d%d%d", &l1, &r1, &l2, &r2);if (get(l1, r1) == get(l2, r2))printf("Yes\n");elseprintf("No\n");}return 0;
}

• 字符串哈希通过前缀哈希+幂次预处理实现O(1)子串比较。

• P的选择和自然溢出是关键优化点。

• 适用于需要频繁比较子串的场景，比直接暴力匹配高效得多。