关于哈希的用法 试读

哈希是字符串的一个东西,比较好用的..可以寻找任意位子的两段是不是相同,相同则哈希值相同..
建议哈希倍数为131,既是131进制数,建议直接unsigned long long作为模数.哈希用途很广的,可以用来排序,求最大回文子串长度...
哈希的存数方法是h[i]=h[i-1]*base+s[i]-'a'+1;//字符串哈希
得到这段哈希值先给大家话一下图罗

下面给大家演示下哈希的实现方法.

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int base=131,N=1e6+5;
ull b[N],h[N];
char s[N];
int get(int l,int r)
{
    return h[r]-h[l-1]*b[r-l+1];
}
int main()
{
    scanf("%s",s+1);
    h[0]=0;b[0]=1;
    int n=strlen(s+1);
    for(int i=1;i<=n;i++)
    {
        b[i]=b[i-1]*base;
        h[i]=h[i-1]*base+s[i]-'a'+1;
    }
    int q,l,r,ll,rr;
    cin>>q;
    while(q--)
    {
       cin>>l>>r>>ll>>rr;
       if(get(l,r)==get(ll,rr)) puts("Yes");
       else                     puts("No");
    }
    return 0;
}

哈希介绍结束了~很简单一个算法,也很好用