字符串哈希

• 0. 概述
• 1. 数据结构
• 2. 求字符串哈希值
• 3. 求字符串字串的哈希值
• 4. 判断两个子串是否相同
• 5. 【例题】洛谷 P3370

视频链接：F02 字符串哈希 bilibili

0. 概述

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

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

   • 定义其 $Hash$ 函数为：$ h(s)=\sum_{i=1}^n s[i]×p^{i-1}(mod M)$
   • 如：字符串 $abc$ ，哈希函数值为 $ap^2+bp^1+c=97×131^2+98×131^1+99$

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

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

   • 巧妙设置 $p$ 和 $M$ 的值，保证 $p$ 和 $M$ 互质
   • $p$ 通常为：$131$ 或 $13331$
   • $M$ 通常取大整数 $2^{64}$，把哈希函数值 $h$ 定义为 $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);
}

5. 【例题】洛谷 P3370

题目链接：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;

打赏