HASH 字符串哈希 映射转化

时间:2023-02-06 14:51:55

哈希HASH的本质思想类似于映射、离散化。

哈希,通过给不同字符赋不同的值、并且钦定一个进制K和模数,从而实现一个字符串到一个模意义下的K进制数上。

它的主要目的是判重,用于$DFS$、$BFS$判重(八数码),字符串判断相等、出现等等。

本篇总结字符串哈希以及一些应用例题。

为什要用字符串哈希?

因为取出一个字符串是$O(n)$的,比较一遍又是$O(n)$的,况且要比较两个甚至多个。这就成了$n^2$级别的了。

那我们比较数字怎么就不用这么麻烦呢?因为数字可以直接比较,(虽然不知道内部是怎么实现的,反正比一位一位比较肯定快)所以我们考虑把字符串映射到数字上。

就有了字符串哈希。

通过字符串哈希,只要题目支持预处理,我们可以$O(n)$预处理之后,$O(1)$进行提取,$O(1)$进行判重。

字符串哈希需要什么?

1.字符。初始坐标无所谓。

2.K进制数,通常选择$131$,$13331$,这两个质数冲突几率很小(不要问我为什么)。

3.取模数,我用过 $1e9+7$,$998244353$,用$2^{64}$也可以,这里利用自然溢出,一般不会有问题。提一句,$unsigned\space long\space long$做减法,即使算出来应该是负数,会自动加上$2^{64}$,相当于$(a+mod-b)%mod$了。没有问题。

处理hash:

1.预处理$K^{len}$ 放入$k[]$中储存。

2.顺便处理$hash[i]=hash[i-1]*K+str[i]$

hash的容器:

1.一个题可能产生很多哈希值。有的时候我们要找一个容器存储。能够比较快速地查询一个$hash$值有没有出现过。

2.比较常用的是$map<ll,bool>$,因为本身map就是映射。

3.但是$map$不但有$logn$,常数也不小。于是就有了hash表。

其实就是对$hash$值再分类存放。就可以避免很多没有意义的查询。

再找一个模数,一般是所有哈希值出现次数的几分之一(数组能开下),可以的话,就取出现次数也行。

然后,哈希值先除以模数,余数就是位置。然后用邻接表存储。

字符串哈希的基本操作:

1.提取:$a[l,r]$段:$hash[r]-hash[l-1]*k[r-l]$ 类似前缀和。

2.插入,同处理。

操作均是$O(1)$

字符串哈希支持的应用操作:

1.判断字符串是否相等。取hash段比较即可,$O(1)$

2.找某两个位置开始的$LCP$(最长公共前缀),二分位置+$hash$判断 $O(logn)$ (长度够小,可用$trie$树,更好的支持多串$LCP$)(当然,如果你会$SA$,这些都是小儿科~)

3.判断两个串字典序大小,找$LCP$,判断下一位大小。$O(logn)$

4.找回文串。但是要正反二分。如果可以预处理的话,当然不如$manacher$。或者你用SA建反串然后找LCP。

哈希冲突

1.由于取模,所以有一定几率,两个不同的串,但是哈希值相同。

我们认为哈希值相同,串就相同了。所以,就会出现错误。

像1e9+7,unsigned long long 这些,都可以特殊构造卡掉。

见bzoj HASH KILLER系列。

2.解决方法:

①取大质数作为模数。$10^{15}$以上的模数更不容易被卡。

②双哈希

即处理两个哈希值。相同的字符串一定两个都相同,因为都是同样的构造方法。

如果哈希值不同,一定是不同的字符串。

这个时候,如果两个串的两个哈希值对应相等,我们就认为相等。否则不等。

这样子冲突的概率就很小了。$1e9+7$,$998244353$的双模数就基本卡不掉了。

字符串哈希例题:

T1:POJ2758

给定一个字符串,要求维护两种操作
在字符串中插入一个字符
询问某两个位置开始的LCP
插入操作<=200,字符串长度<=5w,查询操作<=2w

分析:有人用后缀数组??不会。Splay??不会。

操作小于等于200,直接暴力重构是正解!!

注意:

1.插入字符位置可能远大于len,要向len+1取min

2.询问位置是初始位置,重构的时候,可以暴力循环记录每一个初始位置现在已经变到了第几个位置。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=+;
const int mod=;
const int K=;
ll h[N];
ll c[N];
int n,m;
int len;
int f[N];
int ne[N];
char o[N],a[N];
int main()
{
scanf("%s",o+);
n=strlen(o+);
memcpy(a+,o+,sizeof o);len=n;
//cout<<" lenn "<<len<<endl;
scanf("%d",&m);
for(int i=;i<=n;i++) ne[i]=i;
c[]=;
for(int i=;i<=n+m+;i++) {
c[i]=(c[i-]*K)%mod;
if(i<=n) h[i]=(h[i-]*c[]+(int)o[i])%mod;
}
char ch,op;
int num,x,y;
//cout<<"fir "<<a+1<<endl;
while(m--){
scanf(" %c",&op); if(op=='Q'){
scanf("%d%d",&x,&y);
x=ne[x],y=ne[y];
//cout<<x<<" and "<<y<<endl;
if(a[x]!=a[y]){
printf("0\n");continue;
}
int ans;
int l=,r=min(len-x,len-y)+;
//cout<<" origin "<<l<<" "<<r<<endl;
while(l<=r){
int mid=(l+r)>>;
int ed1=x+mid-;
int ed2=y+mid-;
ll ha1=(h[ed1]+mod-h[x-]*c[mid]%mod)%mod;
ll ha2=(h[ed2]+mod-h[y-]*c[mid]%mod)%mod;
//cout<<mid<<" hash "<<ha1<<" "<<ha2<<endl;
if(ha1==ha2) {
ans=mid,l=mid+;
}
else{
r=mid-;
}
}
printf("%d\n",ans);
}
else{
scanf(" %c%d",&ch,&num);
if(num>len) num=len+;
///add(num);
len++;
for(int i=len;i>=num+;i--) a[i]=a[i-];
a[num]=ch;
for(int i=num;i<=len;i++) h[i]=(h[i-]*c[]+(int)a[i])%mod;
for(int i=n;i>=;i--) {
if(ne[i]>=num) ne[i]++;else break;}
}
//cout<<a+1<<endl;
}
return ;
}

POJ2758

以下是配赠福利

树哈希:

我们知道,一棵无根树可以以任何一个点为根。两个树可能看过去形态不同,但是可能存在固定两个树的根,然后对整个树重新编号,使得完全相同。

求树的同构就是这样。

类似字符串同构,我们也要适用哈希。

模板例题:

BZOJ 4337: BJOI2015 树的同构

50棵树,50个节点。求同构。

方法:
1.对于两个同构的树,存在固定两个树的根,然后对整个树重新编号,使得完全相同。

所以,我们可以对一个树,以每个点为根,然后dfs一遍。

$dfs$的时候,处理子树的$hash$值。

$hash$的$base$值和第几个儿子有关。是各不相同的素数。

然后,对于一个子树,把所有的儿子$hash$值,排序,从小到大合并。

然后对于所有的$hash$值,$sort$一遍。

两个树相同,当且仅当所有的$N$个点的$hash$值对应相同。

我们的$hash$值考虑了深度、每个点节点个数。所以不容易冲突。

2.我们之所以要以每个点为根,然后$dfs$一遍,

是因为可能重新编号后根不知道是哪两个。

但是这样比较暴力。$N^3$

发现,对于一个无根树,重心最多两个。

对于两个同构的树,如果我们把重心的搭配4种枚举一下,那么必然存在一种树的$hash$相同。

所以,可以对每个树以重心扫两边即可。

$hash$的$base$,也可以考虑用欧拉序。