字符串哈希从入门到精通
一、基本概念
字符串哈希是将任意长度的字符串映射为固定长度的哈希值(通常为整数)的技术,核心目标是实现O(1)时间的子串快速比较和高效查询。其本质是通过数学运算将字符串转换为唯一性较高的数值,例如:
其中P为基数(根据题目),M为大质数,s[i]为字符的ASCII值。
二.一般哈希实现
一般哈希的实现有两种方式:
通俗的讲叫:
1.蹲茅坑法
2.拉拉链法
2.1蹲茅坑法
假设你现在要处理19与12(mod 7)
你会发现19与12 mod 7 都是5!
这应该怎么办?
你就可以想象成你要蹲茅坑,5号坑有人了!那你不是得去下一个坑吗!!!
如果5号有19,那么我们就把12入6号;
2.2拉拉链法
你把每个格想象成一个链表,把相同的存进链表里就行。
但是以上的都不重要……
三.字符串哈希
字符串哈希的原理其实很简单,就是把这个字符串看成一个多进制的数,然后将这个数化成十进制数的结果就是哈希的结果。(如同十进制的数字每一个都是唯一的,所以说哈希值不存在重复)
直接上代码!!!
for(int i=0;i<s1.size();i++){
ans=(ans*128+s1[i])%998244353;
//ans*128是将上一位数前移
//最后一般都会取余一个大质数(1e9,998244353)
}
还有一个:
ll geth(int l,int r){
return has[r]-has[l-1]*pw[r-l+1];
//得到这个区间内的哈希值(类似前缀和)
//qw[r-l+1]是为了对齐方便减
}
是不是很简单!!!
四.例题《查字典》
4.1题目
4.2思路
我们先把每个外语单词的哈希值算出来,然后m次输入,再把输入的哈希值算出来,最后遍历哈希数组,有这个哈希值就输出所对应的英文单词,没有就输出“eh”。
4.3代码
#include<bits/stdc++.h>
using namespace std;
long long ans,has[1005],mod=1e9+7,n,m;
string s1[1005],s2[1005],s3;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>s1[i]>>s2[i];
for(int j=0;j<s2[i].size();j++){
has[i]=has[i]*128+1ll*s2[i][j];
}
}
cin>>m;
for(int i=0;i<m;i++){
cin>>s3;
ans=0;
for(int j=0;j<s3.size();j++){
ans=ans*128+1ll*s3[j];
}
bool flag=0;
for(int j=1;j<=n;j++){
if(has[j]==ans){
cout<<s1[j]<<"\n";
flag=1;
}
}
if(flag==0){
cout<<"eh"<<"\n";
}
}
return 0;
}