字符串哈希 学习笔记

· · 算法·理论

哈希

可将复杂的数据压缩：通过哈希函数将其映射成一个整数，即哈希值。
然后利用这个哈希值进行 O(1) 比较、查找或去重。

注意：倘若你的哈希函数不够优秀，可能导致两个不同的数值转换为相同的哈希值，我们称之为冲突。

冲突的存在会导致你的算法出错，所以你必须着手解决它。

字符串哈希基础

当上文的复杂数据为字符串时，
我们称为字符串哈希。

哈希函数的构造

对于字符串 S，我们通常使用多项式哈希计算其哈希值：

\text{hash}(S) = \left( \sum_{i=1}^{|S|} S_i \cdot base^{n-i} \right) \bmod M

公式理解

感性理解

假设我们有一个数组 a=\{2,9,4,0,1,4\}，保证其值域为 0 \sim 9 的整数。
很显然可以用哈希值 294014 来表示它。

原理是将数组的每个元素看作 10 进制数的每一位，并组合起来：

2\times10^5+9\times10^4+4\times10^3+0\times10^2+1\times10^1+4\times10^0 = 294014

迁移运用

字符串是一个字符数组，
而每个字符都可以用 ASCII 码表示为 0\sim 127 之间的整数。

因此，对应的哈希值应该至少是一个 128 进制数，
用每个字符的 ASCII 码作为它的每一位。

注意：计算的结果可能很大，所以我们需要取模。

避免冲突

因为哈希值需要对 M 取模，故哈希值的范围有限。
但字符串的种类却是无限的。

因此冲突不可避免，我们能做的只有减小冲突出现的概率。

数值的选取

底数

底数（进制） base 需大于等于 128。

通常选择 131、137、13331、1145141 等质数。

模数

模数 M 则通常选择 10^9+7、10^9+9、10^9+123、999999937 等质数。

如果想减少码量，可以直接定义哈希值为 unsigned long long 类型，
运用其自然溢出，能轻松实现对 2^{64} 取模。

双值哈希

选择不同的模数和底数，计算两个哈希值，
当且仅当两个哈希值都相等时，才说明字符串相同。

出题人角度

哈希可能出现冲突，使答案错误，
因此字符串哈希不是一个 100\% 正确的算法。

站在出题人角度，他很可能会构造出现冲突的数据，进而卡掉这个不那么正确的算法。

因此我们需要使哈希函数变复杂，来避免冲突，避免被卡掉。

具体方法有很多，比如上面那些。

注意事项

不过不用担心，一般哈希是很难卡的，可以放心使用。

字符串哈希技巧

首先给出几份字符串哈希模版代码：

单值哈希

typedef long long ll;

ll mod = 1000000009,base = 13331;
ll Hash_str(string s) {
    ll h = 0;
    for(char c:s) {
        h = (h*base+c)%mod;
    }
    return h;
}

自然溢出哈希

typedef unsigned long long ull;

ull base = 13331;
ull Hash_str(string s) {
    ull h = 0;
    for (char c:s) {
        h = h*base+(ull)c;
    }
    return h;
}

双值哈希

typedef long long ll;
typedef pair<ll,ll> pll;

ll mod[2] = {1000000009,999999937},base[2] = {13331,1145141};
pll Hash_str(string s) {
    ll h0 = 0,h1 = 0;
    for(char c:s) {
        h0 = (h0*base[0]+c)%mod[0];
        h1 = (h1*base[1]+c)%mod[1];
    }
    return make_pair(h0,h1);
}

前缀哈希

考虑如何快速查询一段子串的哈希值。

定义

用 S_{l,r} 表示字符串 S 从下标 l 到 r 的子串。
则其哈希值可以这样计算：

hash(S_{l,r}) = hash(S_{1,r})-hash(S_{1,l-1})\times base^{r-l+1}

类似于前缀和，
预处理 O(|S|)，查询子串哈希值 O(1)。

::::info[感性理解] 假设我们有一个数组 a=\{2,9,4,0,1,4\}，保证其值域为 0 ~ 9 的整数。
很显然可以用哈希值 294014 来表示它。

那么从下标 3 到 5 的子数组可以表示为 401。
其是由 29401-29\times 10^3 得到的。

那么换到字符串上也是同理。 ::::

Code

单值前缀哈希

typedef long long ll;

ll powb[N],h[N];
ll base = 13331,mod = 1000000007; 
void init() {
    powb[0] = 1; //表示 base^i 
    for(int i = 1; i <= (int)s.size(); ++i) {
        //我的字符串下标是从 1 开始的 
        h[i] = (h[i-1]*base+s[i])%mod;
        powb[i] = powb[i-1]*base%mod;
    }

}
ll Hash_substr(int l,int r) {
    return (h[r]- h[l-1]*powb[r-l+1]%mod+mod)%mod;
}

双值前缀哈希

typedef long long ll;
typedef pair<ll,ll> pll;

pll h[N];
ll mod[2] = {1000000009,999999937},base[2] = {13331,1145141},powb[2][N];
void init() {
    powb[0][0] = powb[1][0] = 1;
    for(int i = 1; i <= (int)s.size(); ++i) {
        h[i].first = (h[i-1].first*base[0]+s[i])%mod[0];
        h[i].second = (h[i-1].second*base[1]+s[i])%mod[1];

        powb[0][i] = powb[0][i-1]*base[0]%mod[0];
        powb[1][i] = powb[1][i-1]*base[1]%mod[1];
    }

}
pll Hash_substr(int l,int r) {
    return make_pair((h[r].first- h[l-1].first*powb[0][r-l+1]%mod[0] +mod[0])%mod[0],
                    (h[r].second- h[l-1].second*powb[1][r-l+1]%mod[1] +mod[1])%mod[1]);
}

二维前缀哈希

若待处理的数据从字符串变为字符矩阵，
即由一维升到二维，该怎么哈希。

可以类比一维前缀和与二维前缀和。

定义

定义 h_{i,j} 表示左上角 (1,1) 到右下角 (i,j) 的子矩阵的哈希值。

具体的，我们先对每一行做一次一维字符串哈希。
对于每一行的哈希值，我们再在纵向上把它们哈希起来，即为二维字符串哈希。

初始化

按照上述过程，
这里提供一种更好写的初始化（不需要容斥）。

for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= m; j ++)
        h[i][j] = h[i][j-1]*base[0]+c[i][j];
for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= m; j ++)
        h[i][j] += h[i-1][j]*base[1];

base[0] 和 base[1] 表示进制，
为了安全性，横向和纵向的进制可以不同。

计算子矩阵哈希值

结合容斥原理，计算左上角 (a,b) 到右下角 (c,d) 的子矩阵的哈希值，

h_{c,d}-h_{a-1,d}\times base_1^{c-a+1}-h_{c,b-1}\times base_0^{d-b+1}+h_{a-1,b-1}\times base_1^{c-a+1} \times base_0^{d-b+1} 
unsigned long long matrix(int a,int b,int c,int d) {
    return h[c][d]
           - h[a-1][d]*powb[1][c-a+1] 
           - h[c][b-1]*powb[0][d-b+1] 
           + h[a-1][b-1]*powb[1][c-a+1]*powb[0][d-b+1];
}
//powb[0][i] 和 powb[1][i] 需要预处理计算
//表示 base[0] 和 base[1] 的 i 次方

注意：
绿色部分乘 base[1]（列进制）的次方，
蓝色部分乘 base[0]（行进制）的次方，
交叉部分被两种进制计算过两次，因此要乘 base[1] 和 base[0]。

感性理解一下，上图的计算结果应为：

123456789-123\times1000000(base_1^2)-1004007\times100(base_0^2)+1\times1000000\times100=000056089

哈希值 000056089 对应

E&F\\ H&I \end{pmatrix}

时间复杂度：O(1)。

Code

单值哈希

ull base[2] = {1145141,13331},powb[2][N];
ull h[N][N];
void init(char c[N][N],int n,int m) {
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++) {
            h[i][j] = h[i][j-1]*base[0]+c[i][j];
        }
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++) {
            h[i][j] += h[i-1][j]*base[1];
        }
    powb[0][0] = powb[1][0] = 1;
    for(int i = 1; i <= max(n,m); i ++) {
        powb[0][i] = powb[0][i-1]*base[0];
        powb[1][i] = powb[1][i-1]*base[1];
    }
}
ull matrix(int a,int b,int c,int d) {
    return h[c][d]
           - h[a-1][d]*powb[1][c-a+1] 
           - h[c][b-1]*powb[0][d-b+1] 
           + h[a-1][b-1]*powb[1][c-a+1]*powb[0][d-b+1];
}

双值哈希

ull base[4] = {1145141,13331,131,137},powb[4][N];
pll h[N][N];
void init(char c[N][N],int n,int m) {
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++) {
            h[i][j].first = h[i][j-1].first*base[0]+c[i][j];
            h[i][j].second = h[i][j-1].second*base[2]+c[i][j];
        }
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++) {
            h[i][j].first += h[i-1][j].first*base[1];
            h[i][j].second += h[i-1][j].second*base[3];
        }
    powb[0][0] = powb[1][0] = powb[2][0] = powb[3][0] = 1;
    for(int i = 1; i <= max(n,m); i ++) {
        powb[0][i] = powb[0][i-1]*base[0];
        powb[1][i] = powb[1][i-1]*base[1];
        powb[2][i] = powb[2][i-1]*base[2];
        powb[3][i] = powb[3][i-1]*base[3];
    }
}
pll matrix(int a,int b,int c,int d) {
    ull fir = h[c][d].first 
              - h[a-1][d].first*powb[1][c-a+1] 
              - h[c][b-1].first*powb[0][d-b+1] 
              + h[a-1][b-1].first*powb[1][c-a+1]*powb[0][d-b+1];
    ull sec = h[c][d].second
              - h[a-1][d].second*powb[3][c-a+1]
              - h[c][b-1].second*powb[2][d-b+1] 
              + h[a-1][b-1].second*powb[3][c-a+1]*powb[2][d-b+1];

    return make_pair(fir,sec);
}

字符串哈希应用

字符串哈希的本质是数据压缩，
其应用也是围绕这个作用展开的。

字符串匹配

在大部分字符串匹配问题中，
哈希都是一个更好理解、更方便快捷的方法。

（前缀哈希的复杂度都 O(1) 了，还用什么 KMP）。

做法

用上述方法求出字符串或字符矩阵的哈希值，
若哈希值相同，则说明它们本身也相等。

一维字符串匹配

P3370 【模板】字符串哈希

CF79C Beaver
解析

二维字符串矩阵匹配

CF228C Fractal Detector
解析

二维矩阵展开为一维字符串

某些题目的字符矩阵不需要或不能使用 O(1) 的前缀哈希。

那么我们可以将二维矩阵展开成一个很长的一维字符串，对该字符串求哈希即可。

这种写法的码量较少

CF54B Cutting Jigsaw Puzzle
解析

哈希思想的其它应用

对于其它非字符串的题目，
若需要数据压缩及匹配，同样可以使用上文讲的多项式哈希。

P8026 [ONTAK2015] Bajtocja
解析