进制哈希学习笔记

哈希是一种映射，将字符串映射到整数上。

由于得到的哈希值都很大，不能直接映射到一个巨大的空间上，所以一般都需要限制空间。限制空间的方法是取模，把得到的哈希值对一个设定的空间大小 $M$ 取模，得到的结果作为索引地址。当然，这样可能会产生哈希冲突。

可以采取一种“隐性取余”的简化方法。取空间大小为 $M= 2^{64}$ ，而 $64$ 是 unsigned long long 型的长度，一个 unsigned long long 型的哈希值 $H$ ，当 $H>M$ 时会自动溢出，等价于自动对 $M$ 取模，这样能够避免低效的取模运算。

BKDRHash

最常用的就是进制哈希 $\mathrm{BKDRHash}$ 。

其计算步骤非常简单。设定一个进制 $P$ ，需要计算一个字符串的哈希值时，把每个字符看作将每个进制位上的一个数字，这个串转换为一个基于进制 $P$ 的数，最后对 $M$ 取模，就得到哦啊了这个字符串的哈希值。

例如计算只由小写字母构成的字符串的哈希值时，以字符串 abc 为例，令进制 $P=131$ ，那么该字符串的哈希值有以下两种计算方法：

1. 把每个字符看做一个数字，即 $a=1,b=2,c=3,\dots,z=26$ ，然后当成 $P$ 进制来算，得到其哈希值为 $1\times 131^2+2\times 131^1+3\times 131^0=17426$ 。
2. 直接把每个字符的 ACSII 码看作代表它的数字也可以，计算得到其哈希值为 $97\times 131^2+98\times 131^1+99\times 131^0=1677554$ 。

进制 $P$ 常用的值有 $31,131,1313,13131,131313$ 等，用这些树值能够有效避免碰撞。

---

例题 洛谷P3370 【模板】字符串哈希

如题，给定 $N$ 个字符串（第 $i$ 个字符串长度为 $M_i$，字符串内包含数字、大小写字母，大小写敏感），请求出 $N$ 个字符串中共有多少个不同的字符串。

思路

直接根据上面的运算来写即可。

这里我采取了第二种计算方法。

代码

#include<bits/stdc++.h>
#define N 10010
#define ull unsigned long long 

using namespace std;

ull h[N];
char s[N];
ull BKDRHash(char *s) {					//计算哈希值
    ull P=131,H=0;
    while(*s) H=H*P+(*s++);
    return H;
}

int main() {
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%s",s);
        h[i]=BKDRHash(s);
    }   
    int ans=0;
    sort(h,h+n);
    for(int i=0;i<n;i++) if(h[i]!=h[i+1]) ans++;
    printf("%d\n",ans);
    system("pause");
    return 0;
}

---

进制哈希的应用

进制哈希的特征：可以按照进制做算术运算。

利用这一特征可以快速计算字符串 S 的所有前缀的哈希值。

例如字符串 $\mathrm{abc}$ ，其前缀有 $\{\mathrm{a},\mathrm{ab},\mathrm{abc} \}$，哈希值计算如下：

1. 计算前缀 $\mathrm{a}$ 的哈希值，得到 $H(a)$ ，时间复杂度 $O(1)$ 。
2. 计算前缀 $\mathrm{ab}$ 的哈希值。 $H(ab)=H(a)\times P+H(b)$ ，时间复杂度 $O(1)$ 。
3. 计算前缀 $\mathrm{abc}$ 的哈希值。 $H(abc)=H(ab)\times P+H(c)$ ，时间复杂度 $O(1)$ 。

所以 $O(|S|)$ 便可以预处理字符串 $\mathrm{S}$ 的所有前缀的哈希值。

计算出所有前缀的哈希值后，能以 $O(1)$ 的复杂度查询它的任意子串的哈希值。

具体实现方式如下：

ull get_hash(ull L,ull R) {return H[R]-H[L-1]*P[R-L+1];}

其中 p[i] 表示 $P$ 的 $i$ 次方。

接下来看进制哈希的一些应用。

---

最长回文串

使用进制哈希能够 $O(n\log n)$ 地求解查找长度为 $n$ 的字符串 $\mathrm{S}$ 中的最长回文子串的问题。

一个回文串是正向读和反向读都相同的串，为了利用哈希找到这样的串，先预处理出字符串 $\mathrm{S}$ 的所有前缀的哈希值，再把 $\mathrm{S}$ 倒过来得到 $\mathrm{T}$ ，预处理出 $\mathrm{T}$ 的所有前缀的哈希值。

如果 $\mathrm{S}$ 的某个子区间是一个回文串，那么对应 $\mathrm{T}$ 的子区间也是回文串，只要比较这两个区间的哈希值是否相等，若相等则说明找到了一个回文串。

这样扫描所有的子区间来查找回文子串，时间复杂度为 $O(n^2)$ 。

考虑用“中心扩展法”，以 $\mathrm{S}$ 的每个字符为中心，左右扩展，如果左右对应的字符相同，就是一个回文串。但如果只是简简单单的扩展，总时间复杂度还是 $O(n^2)$ 。左右两边的扩展的长度显然具有单调性，所以可以考虑用二分优化，这样可以优化到 $O(n\log n)$ 。

---

例题 洛谷P3501 [POI2010] ANT-Antisymmetry

对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。

现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。

思路

其实就是求回文子串个数。

考虑用上面的中心扩展法，不过不是中心，而是左半部分和右半部分。

长度为 $l$ 则说明有 $l$ 个回文子串。

$O(n\log n)$ 二分查找每次累加 $l$ 即可。

代码

#include<bits/stdc++.h>
#define N 500010
#define ll long long 
#define ull unsigned long long 

using namespace std;

const ull P=131;

int n;
char s[N],t[N];
ull hs[N],ht[N],PP[N];
ll ans=0;

ull get_hash(ull *h,int L,int R) {
    return h[R]-h[L-1]*PP[R-L+1];
}

bool check(int pos,int x) {
    return get_hash(hs,pos-x+1,pos)==get_hash(ht,n-pos-x+1,n-pos);
}

void bnry_search(int pos) {
    int l=0,r=min(pos,n-pos);
    while(l<r) {
        int mid=l+r+1>>1;
        if(check(pos,mid)) l=mid;
        else r=mid-1;
    }
    ans+=l;
}

void init() {
    PP[0]=1;
    for(int i=1;i<=n;i++) PP[i]=PP[i-1]*P;
    for(int i=1;i<=n;i++) t[i]=(s[n-i+1]=='0'?'1':'0');
    for(int i=1;i<=n;i++) hs[i]=hs[i-1]*P+s[i];
    for(int i=1;i<=n;i++) ht[i]=ht[i-1]*P+t[i];
}

int main() {
    scanf("%d",&n);
    scanf("%s",s+1);
    init(); 
    for(int i=1;i<=n;i++) bnry_search(i);
    printf("%lld\n",ans);
    system("pause");
    return 0;
}

---

求循环节

例题 洛谷P4391 [BOI2009]Radio Transmission

给你一个字符串 $s_1$，它是由某个字符串 $s_2$ 不断自我连接形成的。但是字符串 $s_2$ 是不确定的，现在只想知道它的最短长度是多少。

思路

可以用哈希较为暴力地解决本题。

首先处理出所有前缀的哈希值。

然后开始枚举 $s_2$ 的长度 $i$ ，从 $1$ 到 $l$ ，每次不断检测后面的连续的长为 $i$ 的区间是否与 $s_1[1\dots i]$ 相等，最后在检测剩下的部分是否与 $s_1$ 的前面对应长度相等即可。

代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long  
#define N 1000010

using namespace std;

inline ll read() {
    ll w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

const ull PP=131;
int l,ans;
char s[N];
ull H[N],P[N];

ull get_hash(int L,int R) {
    return H[R]-H[L-1]*P[R-L+1];
}   

void init() {
    P[0]=1;
    for(int i=1;i<=l;i++) P[i]=P[i-1]*PP;
    for(int i=1;i<=l;i++) H[i]=H[i-1]*PP+s[i];
}

int main() {
    l=read();
    scanf("%s",s+1);
    init();
    for(int i=1;i<=l;i++) {
        bool flag=true;
        for(int j=1;(j+1)*i<=l;j++) {
            if(get_hash(1,i)!=get_hash(1+i*j,i+i*j)) flag=false;
            if(!flag) break;
        }
        int len=l%i;
        if(len&&get_hash(1,len)!=get_hash(l-len+1,l)) flag=false;
        if(flag) {
            ans=i;
            break;
        }
    }    
    printf("%d\n",ans);
    system("pause");
    return 0;
}

---

参考资料

《算法竞赛》罗勇军