首页 > 其他分享 >【学习笔记】哈希

【学习笔记】哈希

时间:2024-08-04 21:41:03浏览次数:14  
标签:int hsh long 学习 cdot cdots 笔记 哈希

【学习笔记】哈希

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;
}

标签:int,hsh,long,学习,cdot,cdots,笔记,哈希
From: https://www.cnblogs.com/FlyPancake/p/18342231

相关文章

  • 第二周--多维特征/2022吴恩达机器学习课程
    示例在先前的模型中,只有一个特征值x(房子的大小),你可以预测y,房子的价格。但是现在你又知道了多个细节。所以我们就需要更多的符号去表示对于的特征,如下:模型对比寻找一种更简单的方法重新写该表达式。向量这种算法叫多元线性回归为了实现这一点,我们有一个技巧叫矢量化......
  • 【机器学习】正则化的基本概念以及正则化成本和梯度的示例
    引言在机器学习中,正则化(Regularization)是一种技术,用于减少模型复杂度,防止过拟合,并提高模型的泛化能力。通过在损失函数中添加一个额外的惩罚项,正则化鼓励模型学习更简单、更平滑的函数,从而在未见过的数据上表现得更好文章目录引言一、正则化1.1正则化的形式1.1.1L1......
  • Python pymodbus类库使用学习总结
    实践环境Python3.9.13https://www.python.org/ftp/python/3.9.13/python-3.9.13-amd64.exepymodbus-3.6.8-py3-none-any.whlhttps://files.pythonhosted.org/packages/35/19/a9d16f74548d6750acf6604fa74c2cd165b5bc955fe021bf5e1fa04acf14/pymodbus-3.6.8-py3-none-any.whl......
  • UE5学习笔记3-关于charactor的相机和弹簧臂组件
    一、环境说明,UE5.4+ vs2022 +win11二、相机和弹簧臂的作用    个人理解上,相机的作用相当于一个视角,我将其理解成是一个人在哪个地方朝向哪个方向看,弹簧臂的用用我将其理解成为一个将人的视角和人物模型或其他模型连接的桥梁三、相机和弹簧臂的代码    ......
  • 学习笔记486—Macbook 咖啡厅麦当劳热点无法认证/连不上的解决方法
    Macbook咖啡厅麦当劳热点无法认证/连不上的解决方法笔者用的设备是MacBookpro14寸,m1pro版本。macos版本为13.2。之前一直碰到在星巴克/麦当劳/tims连不上店铺热点,只能连自己手机或者ipad热点的尴尬情况,翻遍了国内外相关论坛和网站,死活找不到解决方案。今天终于在一个售后维......
  • 深入理解 ReLU 激活函数及其在深度学习中的应用【激活函数、Sigmoid、Tanh】
    ReLU(RectifiedLinearUnit)激活函数ReLU(RectifiedLinearUnit)激活函数是一种广泛应用于神经网络中的非线性激活函数。其公式如下:ReLU(x......
  • Scalable Diffusion Models with Transformers(DIT)代码笔记
    完整代码来源:DiTDiT模型主要是在diffusion中,使用transformer模型替换了UNet模型,使用class来控制图像生成。根据论文,模型越大,patchsize越小,FID越小。模型越大,参数越多,patchsize越小,参与计算的信息就越多,模型效果越好。模型使用了Imagenet训练,有1000个分类,class_labe......
  • docker入门学习
    docker入门学习前言一、简介1.docker是什么2.docker特点及应用3.docker与虚拟机的区别4.docker相关概念理解5.docker网络二、docker安装1.安装2.配置镜像三、docker命令1.服务相关命令2.容器相关命令3.镜像相关命令四、搭建服务测试1.搜索tomcat镜像2.pulltomcat3.查......
  • 【学习笔记】Matlab和python双语言的学习(蒙特卡洛法)
    文章目录前言一、蒙特卡洛二、经典示例:计算圆周率π1.代码实现----Matlab2.代码实现----python三、示例2:三门问题1.代码实现----Matlab2.代码实现----python总结前言通过模型算法,熟练对Matlab和python的应用。学习视频链接:https://www.bilibili.com/video/BV1E......
  • 科大讯飞P30、小度K16、优学派U59区别 2024最具性价比学习机推荐
    科大讯飞AI学习机P30是一款为小学到高中学生设计的全能型学习平板。它配备了6GB的运行内存和256GB的存储空间,能够轻松运行各种学习应用和存储大量学习资料。11英寸的大屏幕采用护眼设计,能够有效减少蓝光辐射,保护学生视力。P30覆盖了从小学到高中的全科目课程,配合科大讯飞的AI技术,......