【C++算法模板】字符串哈希，超详细注释带例题

0）概述

• 字符串哈希即把不同的字符串映射成不同的整数

1. 把字符串映射成一个 p p p 进制数字，对于一个长度为 n n n 的字符串 s s s

   • 定义其 H a s h Hash Hash 函数为： h ( s ) = ∑ i = 1 n s [ i ] × p i − 1 ( m o d M ) h(s)=\sum_{i=1}^n s[i]×p^{i-1}(mod M) h(s)=∑i=1n​s[i]×pi−1(modM)
   • 如：字符串 a b c abc abc ，哈希函数值为 a p 2 + b p 1 + c = 97 × 13 1 2 + 98 × 13 1 1 + 99 ap^2+bp^1+c=97×131^2+98×131^1+99 ap2+bp1+c=97×1312+98×1311+99

2. 如果两个字符串不一样但 H a s h Hash Hash 函数值一样，这样的现象被称作哈希碰撞

3. 解决哈希碰撞的方法（极大程度减少哈希碰撞次数，但还是有可能碰撞）

   • 巧妙设置 p p p 和 M M M 的值，保证 p p p 和 M M M 互质
   • p p p 通常为： 131 131 131 或 13331 13331 13331
   • M M M 通常取大整数 2 64 2^{64} 264，把哈希函数值 h h h 定义为 U L L ULL ULL，对于无符号数，超过则自动溢出，等价于取模了

1）数据结构

const int N=1e5+5; // 最大字符串的个数
const int M=1.5e3+10; // 题目中字符串的最大长度
const int P=131; // 131,13331不容易哈希碰撞

// p[i]:表示p的i次方
// h[i]:表示s[1~i]的哈希值,如h[2]表示字符串s前两个字符组成字符串的哈希值
ULL p[N],h[N];
char s[M]; // 存储字符串
int n;

2）求字符串哈希值

• 求一个字符串的哈希值相当于求前缀和

// 预处理hash函数的前缀和,时间复杂度O(n)
void init() {
	// p^0=1,空串哈希值为0
	p[0]=1,h[0]=0;
	for(int i=1;i<=n;i++) {
		p[i]=p[i-1]*P;	
		h[i]=h[i-1]*P+s[i]; // 前缀和计算公式
	}
}

3）求字符串字串的哈希值

• 求字符串字串的哈希值相当于求区间和

// 计算s[l~r](子串)的hash值,时间复杂度O(1)
ULL get(int l,int r) {
	return h[r]-h[l-1]*p[r-l+1]; // 区间和计算字串的hash值
}

4）判断两个子串是否相同

• 直接计算这两个子串的哈希值即可，若相等说明子串相同，反之亦然

// 判断两个子串是否相同
bool substr(int l1,int r1,int l2,int r2) {
	return get(l1,r1)==get(l2,r2);
}

【例题】洛谷 P3370

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e5+5; // 字符串数量上界
const int M=1.5e3+10; // 单个字符串最大长度
const int P=131; // 131,13331不容易哈希碰撞

// h[i]:表示s[1~i]的哈希值,如h[2]表示字符串s前两个字符组成字符串的哈希值
ULL h[N]; 
char str[M]; // 存储字符串
set<ULL> s; // 存储每个字符串的哈希值,集合自动去重

int n;

// 计算字符串s的哈希值
ULL Hash(char str[]) {
	h[0]=0; // 空串哈希值为0
	int len=strlen(str+1); // 计算长度
	for(int i=1;i<=len;i++) {
		h[i]=h[i-1]*P+str[i];	
	}
	return h[len]; // 返回此串的哈希值
}

int main() {
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) {
		scanf("%str",str+1); // 从下标1开始存
		s.insert(Hash(str)); // 存储答案
	}
	cout<<s.size();
	return 0;
}