#创作计划#字符串哈希详解

༺ཌༀཉི༒白·羊༒༃ༀད༻

2025-09-28 20:55:33

发布于：上海

39阅读

0回复

0点赞

本篇讲解哈希算法，这是一种在很多领域都有运用的算法。

目录

1.简介

2.关键性质

3.核心思想

4.单哈希算法

5.双哈希算法

6.无符号长整型溢出法

Part 1. 简介

哈希算法在编程竞赛中的主要应用是把一个字符串映射为一个数字（通常会取模）来把 $O(n)$ 的字符串比较问题转化为 $O(1)$ 的数字比较（当然预处理不是 $O(1)$ 的）。

Part 2. 关键性质

哈希算法主要有以下性质

确定性
- 相同的输入必定产生相同的哈希值（也是哈希算法的基础）
高效性
- 计算哈希值的过程应该很快
雪崩效应
- 输入的微小变化会导致输出的巨大差异
- 例如" $aello$ "和" $hello$ " 的哈希值应该完全不同
抗碰撞性（这个指标是用来判定哈希冲突的）
- 弱抗碰撞性：给定一个输入，很难找到另一个不同的输入产生相同的哈希值
- 强抗碰撞性：很难找到任意两个不同的输入产生相同的哈希值

Part 3. 核心思想

哈希算法的核心思想在于，将字符串的每个字符对应成0~25的数字，再将整个字符串映射为一个 $k$ 进制数（ $k$ 通常取 $128$ ）模一个大质数（比如 $1e9$ 、 $998244353$ ）。
具体实现不难，只需预处理 $128$ 的幂次就可以轻松实现。

Part 4. 单哈希算法

单哈希算法即只用一个数作为模数。
实现并不难，模板代码就不给了，给出一道例题

Part 5. 双哈希算法

这是我们重点讲解的算法。
要想学习双哈希算法我们首先得了解——

$\Huge 哈希冲突$

相信很多读者会发现：哈希算法是基于映射和取模的，那岂不是很好 $hack$ ？只要构造两个取模后相等的字符串不就好了？没错，这就是哈希冲突，双哈希算法就是用以解决哈希冲突的。

那么我们如何解决哈希冲突呢？很粗暴，就是用两个不同的模数来判断，如果两个字符串所映射的数字模两个数都相等，那么他们大概率就是相等的。

这时候，聪明的同学就说了，主包主包，那还是可以 $hack$ 啊？大家大可放心，到现在还没有人成功 $hack$ 掉双哈希（ $bzoj$ 上就有一道这样的题，一直到它倒闭都没人做出来），因为如果有这样的数据，字符串会长到不可想象，所以双哈希是绝对可靠的。

~~就算不可靠你可以再模一个，自创三哈希~~

注：一个实用技巧，哈希在实战中常常使用前缀的形式，详见后面的代码。

下面给出一道例题
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100009;
int n,m;
struct HASH {
	int sed,mod,h[N],pw[N];
	void init(int sed_in,int mod_in) {
		sed=sed_in,mod=mod_in;
		pw[0]=1;
		for(int i=1; i<N; i++) {
			pw[i]=pw[i-1]*sed%mod;
		}
	}//幂的预处理
	void make(string s) {
		h[0]=s[0]%mod;
		for(int i=1; i<s.size(); i++) {
			h[i]=(h[i -1]*sed%mod+s[i])%mod;
		}
	}//哈希
	int get(int l,int r) {//这就是前缀哈希的查询。
		return (h[r]-h[l-1]*pw[r-l+1]%mod+mod)%mod;
	}
} S1,S2,S3,S4;
bool check(int mid) {
	unordered_set<int>sa,sb;
	for(int i=1; i+mid-1<=n; i++) {
		sa.insert(S1.get(i,i+mid-1));
		sb.insert(S2.get(i,i+mid-1));
	}
	for(int i=1; i+mid-1<=m; i++) {
		if( sa.count(S3.get(i,i+mid-1))&&sb.count(S4.get(i,i+mid-1)) ) {
			return true;
		}
	}
	return false;
}
signed main() {
	string s,t;
	cin>>s>>t;
	n=s.size();
	m=t.size();
	s='?'+s;
	t='?'+t;
	S1.init(128,998244353);
	S2.init(128,1e9+7); 
	S3.init(128,998244353);
	S4.init(128,1e9+7); 
	S1.make(s);
	S2.make(s);
	S3.make(t);
	S4.make(t);
	int l=1,r=min(n,m),ans=0;
	while(l<=r) {
		int mid=(l+r)/2;
		if(check(mid)) {
			ans=mid;
			l=mid+1;
		} else
			r=mid-1;
	}
	cout<<ans;
	return 0;
}

我在其中封装了两个哈希结构，不会封装的也可以分开写。

Part 6. 无符号长整型溢出法

双哈希固然好用，但是实现非常困难~~也没多困难~~，所以，我们隆重推出懒人写法——
无符号长整型法，即 $unsigned$ $long$ $long$ 。

这个算法基于无符号长整型溢出后自动取模的特点，但是有小概率被卡~~CSP被卡别怪我~~

还是给一道例题
代码：

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
int has[1000009],pw[1000009],n,l;
string s;
set<int>st;
int get(int l,int r){
	return has[r]-has[l-1]*pw[r-l+1];
}
signed main() {
	cin>>n>>l>>s;
	pw[0]=1;
	for(int i=1;i<=1000000;i++)
			pw[i]=pw[i-1]*128;
	s='?'+s;
	for(int i=1; i<=n; i++)
		has[i]=(has[i-1]*128+s[i]);
	for(int i=1;i<=n-l+1;i++)
		st.insert(get(i,i+l-1));
	cout<<st.size();
	return 0;
}