字符串哈希
831 字
4 分钟
字符串哈希
基本概念
哈希函数
- 定义：将关键字映射成对应地址的函数，记作 Hash(key)=Addr
- 特性：哈希函数可能会把两个或两个以上的不同关键字映射到统一地址（哈希冲突）
字符串哈希
- 核心思想：将一个字符串用一个整数表示
- 应用场景：字符串匹配，快速比较子串，字符串搜索等
哈希函数设计
常用参数
// p 通常取质数 131 或 13331const int P = 13331; // 或 131
// 利用 unsigned long long 的自然溢出实现自动取模typedef unsigned long long ULL;哈希计算原理
对于字符串“abc”,哈希值计算为：
hash = a × p² + b × p¹ + c × p⁰前缀哈希法
数据结构定义
typedef unsigned long long ULL;const int N = 1e6 + 10, P = 13331;
char s[N]; // 字符串数组，下标从1开始int len; // 字符串长度ULL f[N]; // 前缀哈希数组ULL p[N]; // p的i次方数组初始化处理
void init_hash() { f[0] = 0; p[0] = 1;
for (int i = 1; i <= len; i++) { f[i] = f[i - 1] * P + s[i]; // 计算前缀哈希 p[i] = p[i - 1] * P; // 计算p的幂次 }}获取任意子串哈希值
ULL get_hash(int l, int r) { return f[r] - f[l - 1] * p[r - l + 1];}//假设字符串“abc”,需要子串“bc”哈希，则要“abc”-"a"；注意“a”为高位*过2次（下标为2）//故f[r] - f[l - 1] * p[r - l + 1]-->"abc"-"a"*(a下标)单个字符串哈希计算
ULL get_simple_hash() { ULL ret = 0; for (int i = 1; i <= len; i++) { ret = ret * P + s[i]; } return ret;}//无需计算p[i];完整代码示例
#include <iostream>#include <cstring>using namespace std;
typedef unsigned long long ULL;const int N = 1e6 + 10, P = 13331;
class StringHash {private: char s[N]; int len; ULL f[N], p[N];
public: void init(const char* str) { len = strlen(str); // 字符串下标从1开始 for (int i = 1; i <= len; i++) { s[i] = str[i - 1]; } init_hash(); }
void init_hash() { f[0] = 0; p[0] = 1; for (int i = 1; i <= len; i++) { f[i] = f[i - 1] * P + s[i]; p[i] = p[i - 1] * P; } }
ULL get_hash(int l, int r) { if (l < 1 || r > len || l > r) return 0; return f[r] - f[l - 1] * p[r - l + 1]; }
ULL get_simple_hash() { ULL ret = 0; for (int i = 1; i <= len; i++) { ret = ret * P + s[i]; } return ret; }};
int main() { StringHash sh; sh.init("hello world");
// 获取子串 "hello" 的哈希值 ULL hash1 = sh.get_hash(1, 5); cout << "Hash of 'hello': " << hash1 << endl;
// 获取子串 "world" 的哈希值 ULL hash2 = sh.get_hash(7, 11); cout << "Hash of 'world': " << hash2 << endl;
return 0;}注意事项
- 字符串下标：通常从1开始，避免边界处理问题
- 参数选择：P取质数131或13331，减少哈希冲突
- 溢出利用：ULL类型溢出自动取模2^64
- 哈希冲突：虽然概率很低，但在关键应用中可能需要双哈希
- 初始化顺序：必须先初始化p数组，再计算前缀哈希
应用场景
· 快速比较子串：O(1)时间比较任意两个子串是否相等 · 字符串匹配：Rabin-Karp算法的基础 · 回文判断：结合正向和反向哈希 · 最长公共子串：二分答案+哈希检查（二分）
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
相关文章智能推荐
1
前缀和
算法核心思想 预处理：提前计算并储存数组的累加和，空间换时间； 查询优化：O(n)-O(1); 构建前缀和数组 原数组a[i],前缀和数组f[i]; 区间和查询 查询闭区间[l,r]的和
2
Trie树（字典树）
算法定义：快速插入和查询字符串的数据结构 特点：利用字符串的公告前缀，将字符串组成树形结构 优势：相比map，可以高效查找公共前缀
3
差分
算法核心思想：把「区间 [L,R] 全部元素 +k」 时间优化：O(R−L+1) 降到 O(1) 差分数组 f 是原数组 a 的相邻元素之差序列 差分数组两种构造方式
4
查并集
算法维护“集合”的三件套：查询/合并/判同
5
离散化
算法空间换时间 时间复杂度O（n log n）sort排序
随机文章随机推荐