当前位置:   article > 正文

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

字符串哈希模板

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

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=1ns[i]×pi1(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;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

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]; // 前缀和计算公式
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

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

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

在这里插入图片描述

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

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

  • 直接计算这两个子串的哈希值即可,若相等说明子串相同,反之亦然
// 判断两个子串是否相同
bool substr(int l1,int r1,int l2,int r2) {
	return get(l1,r1)==get(l2,r2);
}
  • 1
  • 2
  • 3
  • 4

【例题】洛谷 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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/521179
推荐阅读
相关标签
  

闽ICP备14008679号