【学习笔记】哈希
Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。
主要用来判重！
如何辨别哈希题？大概就通过一句话：当需要用 \(O(1)\) 的时间快速比较两个 \(O(n)\) 的东西时。应该对大部分题目都生效。
字符串哈希
感觉这一块 OI_wiki 讲得比较清楚。
通常我们采用的是多项式 Hash 的方法，对于一个长度为 \(l\) 的字符串 \(s\) 来说，我们可以这样定义多项式 Hash 函数：
\[f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i} \pmod M \]例如，对于字符串 \(xyz\)，其哈希函数值为 \(xb^2+yb+z\)。
其中 \(M\) 最好是一个质数，\(b\) 选取 \([1, M]\) 中的数（尽量小一点）。
可选取 M = 1145141, 1e7+19, 1e9+9; b = 131, 233, 16943.
当然也可以选择 unsigned long long 自然溢出，但是被卡的概率会大大增加。
询问子串哈希：
令：
\[f(s[1 \dots n]) = f_n(s) = s_1\cdot b^{n-1} + s_2\cdot b^{n-2} + \cdots + s_{n-1}\cdot b + s_n \]求：
\[f(s[l \dots r]) = s_l\cdot b^{r-l} + s_{l+1}\cdot b^{r-l-1} + \cdots + s_{r-1}\cdot b + s_r \]解：
\[f_r(s) = s_1\cdot b^{r-1} + s_2\cdot b^{r-2} + \cdots + s_{r-1}\cdot b + s_r \]\[f_{l-1}(s) = s_1\cdot b^{l-2} + s_2\cdot b^{l-3} + \cdots + s_{l-2}\cdot b + s_{l-1} \]\[f_{l-1}(s) \times b^{r-l+1} = s_1\cdot b^{r-1} + s_2\cdot b^{r-2} + \cdots + s_{l-1}\cdot b^{r-l+1} \]\[f_r(s)-f_{l-1}(s) \times b^{r-l+1} = s_l\cdot b^{r-l} + \cdots + s_r = f(s[l \dots r]) \]注意取模相减时可能出现负数。
贴一个 [NOI2016] 优秀的拆分 的 95pts 暴力代码，回顾一下双哈希：（虽然单哈希也能 95pts）
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 30005;
ll base[N], hsh[N], Base[N], Hsh[N];
const int p1=10000019, p2=1000000009;
const int bs1=233, bs2=16943;
char s[N];
int L[N], R[N];
pair<ll, ll> hshnum(int l, int r){
return {(hsh[r]-hsh[l-1]*base[r-l+1]%p1+p1)%p1, (Hsh[r]-Hsh[l-1]*Base[r-l+1]%p2+p2)%p2};
}
int main(){
base[0] = Base[0] = 1;
for(int i=1; i<N; i++){
base[i] = base[i-1]*bs1%p1;
Base[i] = Base[i-1]*bs2%p2;
}
int T; scanf("%d", &T);
while(T--){
scanf("%s", s+1);
int n = strlen(s+1);
for(int i=1; i<=n; i++){
hsh[i] = (hsh[i-1]*bs1%p1+s[i])%p1;
Hsh[i] = (Hsh[i-1]*bs2%p2+s[i])%p2;
}
for(int i=1; i<=n; i++){
L[i] = R[i] = 0;
for(int j=i-1; j>=1; j-=2){
int mid = (i+j)/2;
if(hshnum(j, mid) == hshnum(mid+1, i)) L[i]++;
}
for(int j=i+2; j<=n; j++){
int mid = (i+j+1)/2;
if(hshnum(i+1, mid) == hshnum(mid+1, j)) R[i]++;
}
}
ll ans = 0;
for(int i=1; i<=n; i++)
ans += L[i]*R[i];
printf("%lld\n", ans);
}
return 0;
}
允许 \(k\) 次失配的字符串匹配：
“模板”题：P3763 [TJOI2017] DNA
大差不差，主要是限定了 \(k=3\) 以及只有 4 种字符。
枚举源串的子串，尝试比对出前三个不同的地方，最后一段如果能匹配上那么这个子串就是一个答案，反之则不是。如果还没找到三处不同就已经匹配完整个目标串了，那么这个子串也是一个答案。
哈希的匹配具有单调性。具体来讲，如果两个字符串的前 \(l\) 个字符可以匹配上，那么前 \(l−1\) 个字符也可以匹配上；如果两个字符串的前 \(l\) 个字符不能匹配上，那么前 \(l+1\) 个字符也不能匹配上。
考虑二分，二分出前三个不同的地方，如果匹配完了就结束二分并累加答案，否则判断剩余部分是否匹配即可。
总的时间复杂度为 \(O(m+kn\log_2m)\)。其中 \(n\) 为源串长度，\(m\) 为目标串长度。
另外此题 KMP 不可做。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
const int bs = 233, p = 1e9+9;
ll base[N], hsha[N], hshb[N];
int hshnum(ll hs[], int l, int r){
return (hs[r]-hs[l-1]*base[r-l+1]%p+p)%p;
}
int lcp(int x, int y, int rt){
int lt=0, ans;
while(lt<=rt){
int mid = (lt+rt)>>1;
if(hshnum(hsha, x, x+mid-1)==hshnum(hshb, y, y+mid-1)){
ans = mid;
lt = mid+1;
} else{
rt = mid-1;
}
}
return ans;
}
bool check(int l, int ed){
int st = 1, r = l+ed-1;
// st 是目标串的头，l 是当前子串的头
for(int i=1; i<4; i++){ // 允许失配至多 3 次
int t = lcp(l, st, ed-st+1); // 二分找当前字串与目标串的最长的相同长度
// 跳过失配的字符
l += t+1;
st += t+1;
if(st > ed) return true;
}
return hshnum(hsha, l, r) == hshnum(hshb, st, ed);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T; cin>>T;
base[0] = 1;
for(int i=1; i<N; i++) base[i] = (base[i-1]*bs)%p;
while(T--){
string a, b; cin>>a>>b;
int n = a.length(), m = b.length();
if(n < m){cout<<"0\n"; continue;}
a = ' '+a, b = ' '+b;
for(int i=1; i<=n; i++)
hsha[i] = (hsha[i-1]*bs%p + a[i])%p;
for(int i=1; i<=m; i++)
hshb[i] = (hshb[i-1]*bs%p + b[i])%p;
int ans = 0;
for(int i=1; i+m-1<=n; i++){
if(check(i, m)) ans++;
}
cout<<ans<<"\n";
}
return 0;
}
集合哈希
集合与序列的不同点在于，集合是无序的，也就是说，序列要求每个位置一一相等，而集合只需要对应的元素出现次数相等即可。
此时的哈希函数一般可以表示成如下形式：\(h(\{a_n\})=\sum\limits_{i=1}^nh^{\prime}(a_x)\)。
特殊地，常用的哈希函数有两种：
-
随机权值哈希，即我们给每个元素 \(x\) 赋一个随机数 \(r_x\)，然后 \(h(\{a_n\})=\sum\limits_{i=1}^nr_{a_i}\)。
-
将原集合映射成一个 \(01\) 序列，即若该元素 \(x\) 出现在集合中，第 \(x\) 位置为 \(1\)，否则为\(0\)，然后对得到的 \(01\) 序列进行字符串哈希即可；如果原集合是可重集，那么对应的，原来 \(01\) 的每个位置上保存每个元素的出现次数即可，也就是哈希函数 \(h(\{a_n\})=\sum\limits_{i=1}^nbase^{a_i}\)。
CF1175F The Number of Subpermutations
题目大意：给定数组 \(a_1,a_2 \cdots a_n\)，若子序列 \(a_l,a_{l+1}\cdots a_{r}\) 满足 \(1,2\cdots r-l+1\) 所有整数各出现一次，则称其为这个数组的一个子排列。求这个数组子排列个数。
因为异或满足结合律与交换律，与顺序无关。所以可以考虑异或哈希。
为了避免重复，先将原数组的值随机映射到一个对应的数值。
我们考虑枚举所有 \(a_i = 1\) 的位置为左端点，向右搜索能达到的最大值，用这个最大值当做序列的长度，设这个最大值为 \(m\)，并判断序列内的异或和是否与前 \(m\) 个元素的异或和相等即可。
枚举所有 \(a_i = 1\) 的位置为右端点时只要将序列倒转重新做一次前缀和再枚举就好了。
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
const int N = 3e5+5;
ull hsh[N]; // 将 a 数组中的值随机映射，保证第 i 个数只能由前 i 个 a[i] 异或得到，而不能由其它数字异或得到
ull pre[N]; // 前缀异或和
ull num[N]; // 1 ~ n 的前缀异或和
int n, a[N];
int calc(int pos){
int res = 0, mx = 1;
for(int i=pos+1; i<=n&&a[i]!=1; i++){
mx = max(a[i], mx);
if(i>=mx && i-pos+1<=mx && num[mx]==(pre[i]^pre[i-mx]))
res++;
}
return res;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
random_device seed;
mt19937_64 rnd(seed());
cin>>n;
generate(hsh+1, hsh+1+n, rnd);
for(int i=1; i<=n; i++){
cin>>a[i];
num[i] = num[i-1]^hsh[i];
pre[i] = pre[i-1]^hsh[a[i]];
}
int ans = 0;
for(int i=1; i<=n; i++){
if(a[i] == 1) ans += calc(i)+1; // 单独一个1的贡献
}
reverse(a+1, a+1+n);
for(int i=1; i<=n; i++)
pre[i] = pre[i-1]^hsh[a[i]];
for(int i=1; i<=n; i++){
if(a[i] == 1) ans += calc(i);
}
cout<<ans;
return 0;
}
树哈希
本质上还是集合哈希。
树哈希是哈希中的一个种类，这里先给出哈希函数（以下均省略取模）：
\[{\rm treehash}(u) = \sum {\rm xorshift}({\rm treehash}(v)) \]其中 xorshift 是一种基于位操作的伪随机数生成算法。
树同构是树哈希与换根 dp 的结合。
设 \(g[u]\) 是以 \(u\) 为根的子树的 hash 值之和。使用上式计算即可。
再设 \(f[u]\) 为以 \(u\) 为根的整棵树的 hash 值。
可得：
\[f[u]={\rm xorshift}(f[fa]-{\rm xorshift}(g[u]))+g[u] \]可以理解为原来的 \(f\) 减去现在的子树 \(u\) 的 \({\rm xorshift}\) 的贡献，把剩下的 \({\rm xorshift}\) 就是把 \(fa\) 当成子树的贡献。再加上 \(g[u]\)，就是以 \(u\) 为根时整棵树的 hash 值。
P5043 【模板】树同构
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
const int RP = 1145141919;
int n, m;
bool flag;
vector<int> g[55];
int sz[55], hsh[55], f[55], rt;
set<int> S[52];
int xor_shift(int x){
x ^= RP;
x ^= x<<13;
x ^= x>>7;
x ^= x<<17;
return x;
}
void getHash(int u, int fa){
hsh[u] = 1;
for(int v : g[u]){
if(v == fa) continue;
getHash(v, u);
hsh[u] += xor_shift(hsh[v]);
}
}
void dfs(int u, int fa){
if(fa == 0)
f[u] = hsh[u];
else
f[u] = xor_shift(f[fa]-xor_shift(hsh[u])) + hsh[u];
for(int v : g[u]){
if(v == fa) continue;
dfs(v, u);
}
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>m;
for(int i=1; i<=m; i++){
cin>>n;
rt = 0;
for(int i=1; i<=n; i++)
g[i].clear();
for(int j=1; j<=n; j++){
int x; cin>>x;
if(x){
g[x].push_back(j);
g[j].push_back(x);
}
else rt = j;
}
getHash(rt, 0);
dfs(rt, 0);
int ans = i;
for(int j=1; j<=n; j++)
S[i].insert(f[j]);
for(int j=1; j<=n; j++){
for(int k=1; k<m; k++){
if(S[k].count(f[j]))
ans = min(ans, k);
}
}
cout<<ans<<"\n";
}
return 0;
}