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

哈希学习笔记

时间：2024-01-29 20:01:27浏览次数：24  
标签：Hash int text 笔记 学习 long 哈希 字符串 getchar

定义与基本求法

  • 定义：用于用一个进制数表示一个字符串，以方便存储和判断两字符串是否相等。

  • 基本求法：

    • 联系十进制，如 \(1234\) 即 \(1\times 10^3+2\times10^2+3\times10+4\)

      同样的对于一个字符串，去一个大于其中任意字符（\(\text{ASCII}\)码）的数 \(base\) 作为进制。

      也就有了 \(\text{Hash}(s)=\sum\limits_{i=1}^ns_i\times base^{n-i}\)

      也许与十进制有所不同但大体相似的，因为这是比较容易计算的一种方式。

    • 求单个字符串的 \(\text{Hash}\)：

      根据上式，代码如下：

      int get_hash(string s)
{
    int res=0;
    for(int i=0;i<s.size();i++)
        res=res*b[1]+s[i];
    return res;
}

    • 对于区间查询每次跑一遍显然不可，所以对于需要区间查询的字符串，记录下每一位的前缀和。

      • 代码如下：

        void Hash(string s)
{
    int l=s.size();
    for(int i=0;i<l;i++)
        h[i]=h[i-1]*b[1]+s[i];
}

      • 至于如何求出区间的 \(\text{Hash}\) ，参考前缀和，得出：

        \(\text{Hash}[l:r]=h_r-h_{l-1}\times base^{r-l+1}\)

        int ask(int l,int r)
{
    return h[r]-h[l-1]*b[r-l+1];
}

      • 由此发现，\(\text{base}\) 的次方也是需要预处理的：

        void Base(int n)
{
    ba[1]=233;
    for(int i=2;i<=n;i++)
        ba[i]=ba[i-1]*ba[1];
}

    以上是基本的几个求法。

  • 关于取模与进制——错误率

    • 进制：一个严格大于每一个字符 \(\text{ASCII}\) 码的质数，普遍意义上质数越可能越不易出错，但同时也会有弊端，通常取 \(233,131,137,1e9+7\) 等，也可以在质数大全中选取一个不常见质数防止被卡。

    • 取模：\(\text{Hash}\) 显然是极大的，需要取模，但同时取模就可能造成误差从而出错，通常使用的 \(1e9+7\) 有时可能会被卡掉，在这种情况下就需要换一个更加不常见的质数，或采取如下两种方法：

      1. 双模数：构造两个 \(\text{Hash}\) ，分别模不同的数，在判断两字符串相等时，满足两组 \(\text{Hash}\) 均相等再判断其为相等的。
      2. 自然溢出，即对 \(2^{64}\) 取模，使用 \(unsigned~long~long\) 即可，但同时不可瞎用，通常更不易被卡，但正确率小于双模数，但常熟小于双模数，更快速一些。且更好打。

    • 错误率：\(\text{Hash}\) 是一种存在错误率的算法，其错误率为多少此处不再考虑，但是在大量数据下，极小的概率就变得很有可能，对此选取一个恰当的模数与进制是十分必要的，对此每一道题不一定只有一个进制，也不一定只有一个模数。这属于 \(\text{Hash}\) 的一个局限型，所以在可以使用别的算法情况下，如果明确 \(\text{Hash}\) 会被卡掉，则不要使用该算法。

例题

\(Bovine~Genomics\)

  • 题目链接

  • 题面：

    给定 \(n\) 个 \(A\) 串和 \(n\) 个 \(B\) 串，长度均为 \(m\) ，求一个最短的区间 \([l,r]\) ，使得不存在一个 \(A\) 串 \(a\) 和一个 \(B\) 串 \(b\) ，使得 \(a[l,r]=b[l,r]\) ，求这个区间长度。

  • 解法：

    考虑二分区间长度，重点在于 \(check\) 函数。

    枚举左端点，右端点与之对应，求出每个区间的 \(\text{Hash}\) ，使用 \(map\) ，存入 \(A\) 组的 \(\text{Hash}\) 值，用于判断是否有 \(B\) 组的 \(\text{Hash}\) 值与之相等。

    同时一点注意理解题意，在这一次 \(check\) 中，长度为 \(x\) 的所有区间中，有一组满足即可，并非需要全部满足。

    本题告诉我们，\(\text{Hash}\) 是可以开任意维的，可以分别维护横坐标、纵坐标、所在分组等。

  • 代码如下：

    #include<bits/stdc++.h>
#define int unsigned long long 
#define endl '\n'
using namespace std;
const int N=510;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
int n,m,h[2][N][N],ba[N],ans;
string a[N],b[N];
map<int,bool>v;
void Hash(int d,int id,string s)
{
    int l=s.size();
    for(int i=0;i<l;i++)
        h[d][id][i]=h[d][id][i-1]*ba[1]+s[i];
}
void Base(int n)
{
    ba[1]=233;
    for(int i=2;i<=n;i++)
        ba[i]=ba[i-1]*ba[1];
}
bool check(int x)
{   
    for(int l=0,r=l+x-1;r<m;l++,r++)
    {
        int flag=0;
        v.clear();
        for(int i=1;i<=n;i++)
            v[h[1][i][r]-h[1][i][l-1]*ba[x]]=1;
        for(int i=1;i<=n;i++)
            if(v[h[0][i][r]-h[0][i][l-1]*ba[x]])
                flag=1;
        if(!flag) return 1;
    }
    return 0;
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    read(n),read(m);
    Base(N-1);
    for(int i=1;i<=n;i++)
        cin>>a[i],
        Hash(1,i,a[i]);
    for(int i=1;i<=n;i++)
        cin>>b[i],
        Hash(0,i,b[i]);
    int l=1,r=m,mid;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    cout<<ans;
}

企鹅

  • 题目链接

  • 题面：

    给定几组字符串，求存在几组仅有一个字符不相等 （相等定义为字符与位置均相等）的字符串，保证不存在另个完全相等的字符串。

  • 解法：

    首先维护每一个字符串的 \(\text{Hash}\) 。

    枚举哪一个位置的字符被统一挖掉，之后比较其他位置的 \(\text{Hash}\) 值是否相等。

    至于如何比较剩下的，可以考虑再维护后缀和（当然也可以不维护，用前缀和导出后缀和，但会麻烦容易出错）。那么该字符以前的前缀和和该字符以后的后缀和加在一起构成一个新的值。

    而此处便出现了误差，所以我们对前缀后缀加在一起时分别再乘上不同的进制，从而减小错误率。

    那么我们这么做还有一个原因，方便比较，求出这个新值后，进行排序，从而只需要和旁边一个比较从而使其从 \(O(n)\) 比较变为 \(O(1)\) 比较。

    与此同时，这么做还方便求最后的结果，如果 \(A,B\)、\(B,C\) 分别相等（挖出一字符后），那么 \(A,B,C\) 分别互相相等，那么统计到 \(C\) 的时候，直接将其加上到上一个数为止连等的个数即可；如果遇到不等的，刷新连等的个数。

  • 代码如下：

    #include<bits/stdc++.h>
#define int unsigned long long 
#define endl '\n'
using namespace std;
const int N=3e4+10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
int n,m,S,b[N],b2[N],h[N][210],h2[N][210],ans,ss[N];
string s[N];
map<int,bool>v;
void Hash(int id,string s)
{
    int l=s.size();
    for(int i=0;i<l;i++)
        h[id][i]=h[id][i-1]*b[1]+s[i];
    for(int i=l-1;i;i--)
        h2[id][i]=h2[id][i+1]*b2[1]+s[i];
}
void Base(int n)
{
    b[1]=233,b2[1]=211;
    for(int i=2;i<=n;i++) 
        b[i]=b[i-1]*b[1],
        b2[i]=b2[i-1]*b2[1];
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    Base(N-1);
    read(n),read(m),read(S);
    for(int i=1;i<=n;i++)
        cin>>s[i],
        Hash(i,s[i]);
    for(int l=0;l<m;l++)
    {
        for(int i=1;i<=n;i++)
            ss[i]=h[i][l-1]*131+h2[i][l+1]*137;
        stable_sort(ss+1,ss+1+n);
        int sum=1;
        for(int i=2;i<=n;i++)
            if(ss[i]==ss[i-1]) 
                ans+=sum,
                sum++;
            else sum=1;
    }
    cout<<ans;
}

\(str\)

  • 题目链接

  • 题面：

    现有一字符串 \(s\) ，另外给定 \(n\) 组，每一组有多个字符串，将其每组选一个拼成 \(s\) 。求有多少种可能的情况。

  • 解法：

    \(\text{DP}\) 。

    \(f_{i,j}\) 表示拼到第 \(i\) 组的字符串，拼在右端点在 \(j\) 的位置上，此时的可能情况。

    显然拼第 \(0\) 个的时候，可能情况初始化为 \(1\) 。

    那么如果可以匹配，到这里的可能情况便是拼到 \(i-1\) 组时右端点与现左端点相连的可能情况加上到这里来，即：

    f[i][r]=(f[i][r]+f[i-1][l])%P;

    \(r\) 值当前右端点，\(l\) 值上一个区间的右端点，也是该区间左端点 \(-1\) 。当然，\(r,l\) 同时枚举。

    最后拼完第 \(n\) 组后，其第 \(n\) 组右端点位于所有位置的可能情况加在一起即可。

    同时需要判断是否拼到这个位置可以匹配，就需要用到 \(\text{Hash}\) ，不匹配跳过，枚举下一个 \(l,r\) 即可，这不是难点，难点在于 \(\text{DP}\) 。

  • 代码如下：

    #include<bits/stdc++.h>
#define int unsigned long long 
#define endl '\n'
using namespace std;
const int N=5e5+10,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
int n,ans,h[N],b[N],f[110][N];
string s;
void Hash(string s)
{
    int l=s.size();
    for(int i=0;i<l;i++)
        h[i+1]=((h[i]*b[1])%P+s[i])%P;
}
void Base(int n)
{
    b[1]=233;
    for(int i=2;i<=n;i++)
        b[i]=(b[i-1]*b[1])%P;
}
int get_hash(string s)
{
    int res=0,l=s.size();
    for(int i=0;i<l;i++)
        res=((res*b[1])%P+s[i])%P;
    return res;
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    Base(N-1);
    read(n);
    cin>>s;
    Hash(s);
    int m=s.size();
    for(int i=0;i<=m;i++) f[0][i]=1;
    for(int i=1;i<=n;i++)
    {
        int a;
        read(a);
        for(int j=1;j<=a;j++)
        {
            cin>>s;
            int len=s.size(),hh=get_hash(s);
            for(int l=0,r=len;r<=m;l++,r++)
            {
                if((h[r]-(h[l]*b[len])%P+P)%P!=hh)
                    continue;
                f[i][r]=(f[i][r]+f[i-1][l])%P;
            }
        }
    }
    for(int i=1;i<=m;i++)
        ans=(ans+f[n][i])%P;
    cout<<ans;
}

通配符匹配

  • 前言：深痛教训

  • 题目链接

  • 题面：

    \(*\) 可替代一串字符（包括空串），\(?\) 可替换单个字符，给定一包含上述符号和小写字母的字符串和 \(n\) 组只包含小写字母的字符串，判断每一组是否可以匹配带符号的一组（即上述条件下，两字符串相等）。

  • 解法：

    1. \(\text{DP}\) 是可以的，但是我的 \(\text{DP}\) 不够好必须每一组都跑一遍 \(n^2\) 的 \(\text{DP}\) ，于是就超时了，但总体思路是对的，想要了解参考其他题解，同时，数组开不下是可以滚掉一维的。

    2. 爆搜

      DP没过爆搜能过太抽象了

      这题和 \(\text{Hash}\) 没有半毛钱关系，但是毕竟是到紫，放这里了就也写了吧。

      至于 \(dfs\) 怎么写看代码注释会更容易理解一些。

      复杂度看似很高，但是每次刚搜一下就已经退出来了，所以复杂度其实没多高，所以能过。

  • 代码如下：

    #include<bits/stdc++.h>
#define int long long //qwq千万别开unsigned，至于为什么见上面链接——深痛教训。
#define endl '\n'
using namespace std;
const int N=3e5+10,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
char s[N],t[N];
int q,n,m;
bool ask(int x,int y)//x是s的长度，y是t的长度，从后往前搜，更方便准确。
{
    if(y==0)//当t搜完了。
    {
        for(int i=1;i<=x;i++)
            if(s[i]!='*')
                return 0;//如果s还没搜完，且还存在不是*的元素，则匹配失败。
        return 1;//否则匹配成功。
    }
    if(x==0) return 0;//现在t还没有搜完，s先搜完了，显然无法匹配。
    if(s[x]!='*')//如果现元素不是*，正常搜。
        return (s[x]==t[y]||s[x]=='?')&&ask(x-1,y-1);//如果他现在这一位可以匹配（包括？的情况），若继续往前搜仍旧匹配，则匹配成功，否则匹配失败。
    else //如果是*
    {
        for(int i=y;i>=0;i--)//从当前元素开始一直往前，但凡截到某一位置能够继续匹配s上一位了，那么这个*就是匹配上了。
            if(ask(x-1,i))
                return 1;
    }
    return 0;//不然就是无法匹配了。这个放在上一个括号内也对，但是会有编译警告。
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    scanf("%s",s+1);
    n=strlen(s+1);
    read(q);
    while(q--)
    {
        scanf("%s",t+1);
        m=strlen(t+1);
        cout<<(ask(n,m)?"YES":"NO")<<endl;
    }
}

\(Censoring\)

  • 题目链接

  • 题面：

    给出两个字符串 \(s\) 和 \(t\)，每次从前往后找到 \(s\) 的一个子串 \(a=t\) 并将其删除，空缺位依次向前补齐，重复上述操作多次，直到 串中不含 \(t\) 串。输出最终的 \(s\) 串。

  • 解法：

    至于怎么向前补齐，不难想到栈，而判断是否包含 \(t\) 用 \(\text{Hash}\) 就可以了。

    栈最好用数组模拟，这样可以直接将 \(len\) 个元素弹出，（ \(len\) 指 \(t\) 串长度 ），不然只能一个一个弹，遍没有了意义。

  • 代码如下:

    #include<bits/stdc++.h>
#define int unsigned long long 
#define endl '\n'
using namespace std;
const int N=3e6+10,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
char s[N],a[N],b[N];
int n,m,tot,h[N],hb,ba[N];
void Hash()
{
    for(int i=1;i<=m;i++)
        hb=hb*ba[1]+b[i];
}
void Base(int n)
{
    ba[1]=233317;
    for(int i=2;i<=n;i++) 
        ba[i]=ba[i-1]*ba[1];
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    Base(N-1);
    cin>>a+1>>b+1;
    n=strlen(a+1),m=strlen(b+1);
    Hash();
    for(int i=1;i<=n;i++)
    {
        s[++tot]=a[i];
        h[tot]=h[tot-1]*ba[1]+a[i];
        if(h[tot]-h[tot-m]*ba[m]==hb)
            tot-=m;
    }
    for(int i=1;i<=tot;i++)
        cout<<s[i];
}

总结

至于例题就这么多，主要选取典型且有一定难度的例题，而 \(\text{Hash}\) 的用途还非常广泛，虽然 \(luogu\) 被禁了，别的网站也还有好多不错的题，但这里不整理了，主要因为纯板子过于简单，或者有用更好的算法去做，如在做 \(kmp\) 时会发现好多题都可以用 \(\text{Hash}\) 水过，当然这样的题也是不典型的。\(\text{Hash}\) 中也不乏难题，上面几道非蓝即紫，都是存在不小难度的，尤其是三道大紫题，也是调了好久好久才调出来的。\(\text{Hash}\) 的做法也还有很多扩展，多半时容易理解的，比如和二分、map、栈等、DP等同时使用。后续好多题都是能用 \(\text{Hash}\) 解决的，但不优，且存在错误率，故不再赘述。但同时 \(\text{Hash}\) 仍是一种优秀、应用广泛且相比之下容易理解的一个算法，必须牢牢掌握。还有一种基于哈希的数据结构——哈希表，这里暂时不做整理。

标签：Hash,int,text,笔记,学习,long,哈希,字符串,getchar
From： https://www.cnblogs.com/Charlieljk/p/17995180

相关文章

  • 《构建之法》读书阅读笔记一
     第一章概论：1.“软件=程序+软件工程”问题：程序与软件的区别是什么？回答：以前我总是分不清何为程序,何为软件，一直以为比较完善的程序就是一个软件。于是，我上网查了资料，更加明确两者的区别：程序（program）是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。为进......
  • 《构建之法》读书笔记二
    第二章个人技术与流程1.2.1.1用VSTS写单元测试在该部分，举的例子是用c#写的，因为之前并没有了解这部分的内容，所以，看起书来不是很懂。希望老师在上课时能用同学们学过的Java或者c语言举例给同学们讲解一下。2.“最好在设计的时候就写好单元测试，这样单元测试就能体现API的语义如......
  • DHCN论文阅读笔记
    Abstract基于会话的推荐（SBR）侧重于在某个时间点的下一项项目预测。近年来，基于图神经网络的SBR方法将项目转换为成对的关系，忽略了项目之间复杂的高阶关系。超图提供了一种捕获非成对关系的自然方法。在本文中，我们通过将基于绘画控制的数据建模为一个超图。提出了一个超图卷积网络来......
  • 1.29学习进度
    datafram的组成在结构层面：   structtype对象描述整个datafrme的表结构   structfield对象描述一个列的信息在数据层面：   row对象记录一行数据   column对象记录一列数据并包含列的信息2.dataframe的代码构建–基于rdd方式   dataframe对象可以从rdd转换而来，都......
  • Imdeploy笔记
    Smiling&Weeping----天气不好的时候，我会小心地把自己心上的裂缝补起来。为什么？... LMDeploy的量化和部署1环境配置2服务部署2.1模型转换2.1.1在线转换2.1.2离线转换2.2TurboMind推理+命令行本地对话2.3TurboMind推理......
  • Maven学习之路--依赖范围scope 对于该包的依赖范围作用域，取值有：test、compile、provid
    Maven学习之路--依赖范围scope对于该包的依赖范围作用域，取值有：test、compile、provided、runtime。scope默认取值为compile。\   <scope></scope>表示对于该包的依赖范围作用域，取值有：test、compile、provided、runtime。scope默认取值为compile。<scope>test</scope>。te......
  • 构建之法的读书笔记与读后感2
    软件工程师的成长个人能力的衡量与发展，IC在团队中的流程，初级软件工程师的成长以及工作量和质量的衡量（PSP认为的4个因素），TSP对团队成员的要求（交流、说到做到、接受团队赋予的角色并按角色要求工作、全力投人团队的活动、按照团队流程的要求工作、准备、理性地工作）。软件工程师的......
  • 软件测试学习笔记丨Charles_Mock实战
    Charles_Mock实战1.电脑端抓包抓取雪球Web端搜索接口数据查看接口响应状态码与使用的协议版本查看请求参数与json格式的响应内容快速过滤雪球域名的接口进行弱网测试，选择弱网模式为256kbpsProxy→ThrottleSetting，然后选择EnableThrottling弱网前弱网后2.App抓包抓取......
  • MarkDown的使用学习记录
    标题一级标题的形成：“井号”+“空格”+“标题”二级标题的形成：“井号”+“井号”+“空格”+“标题”三级标题的形成：“井号”+“井号”+“井号”+“空格”+“标题”（以此类推，最多有六级标题）字体粗体:在字的两边各加两个*斜体：在字的两边各加一个*斜体加粗：在字的两边各加三个......
  • 1/29 学习进度笔记
    SparkSQL数据清洗API前面我们处理的数据实际上都是已经被处理好的规整数据，但是在大数据整个生产过程中，需要先对数据进行数据清洗，将杂乱无章的数据整理为符合后面处理要求的规整数据。去重方法dropDuplicates功能:对DF的数据进行去重,如果重复数据有多条，取第一条缺失值处理drop......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99