哈希

· · 个人记录

哈希

选取一个指质数为底数base（通常取131,13331，1e9+7,1e9+9），一个模数（通常取 unsigned long long 中自然溢出中的2^{64}）。
一个字符串d长度为n，哈希值为h_n=\sum s_i \times base^i。
它的子串s-t的哈希值为h_r-h_l\times base^{r-l+1}。
所以我们先预处理出base的次方值，方便用O(1)时间计算子串哈希值。
为了防止哈希值重叠，我们可以使用两个哈希值作为比较参考，即改变底数base。
一种推导哈希式子的办法：把底数看成10手算。

模板：

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
const int MAXN=1e6+1;
char s1[MAXN],s2[MAXN];
int lena,lenb,ans=0;
ull b=13331,p[MAXN],h[MAXN],hb;
int main() {
    scanf("%s%s",s1+1,s2+1); p[0]=1;
    lena=strlen(s1+1); lenb=strlen(s2+1);
    for(int i=1; i<=1e6; i++) p[i]=p[i-1]*b;
    for(int i=1; i<=lena; i++) {
        h[i]=h[i-1]*b+ull(s1[i]-'A'+1);
    }
    for(int i=1; i<=lenb; i++) {
        hb=hb*b+ull(s2[i]-'A'+1);
    }
    for(int i=0; i<=lena-lenb; i++) {
        if(hb==h[i+lenb]-h[i]*p[lenb]) ans++;
    }
    printf("%d\n",ans);
    return 0;
}

练习1：POI 2012 A Horrible Poem

题意：求子串最短循环节的长度
先用线性筛质数求出每个数的最小质因数g_i。
然后对于子串 s-t 它的最小循环节是它的一个因数。
有结论：对于长度l如果不是循环节，那么l的因数也不是循环节。
再把 l 及 \dfrac{l}{g_l} 及\dfrac{\dfrac{l}{g_l}}{g_\frac{l}{g_l}}......处理出来。
然后就对于长度l，如果\dfrac{l}{g_l}不是循环节，那么l不变，准备除以下一个质因数，否则将l赋值为\dfrac{l}{g_l}，储存答案。
这样直到l=1就可以得到答案。
对于l是否是循环节，只需判断s ~ t-l与 s+l ~ t是否相等，用字符串哈希可以解决。 

#include<algorithm>
#include<cstdio>
#include<iostream>
using namespace std;
typedef unsigned long long ull;
const int MAXN=1e6+1;
ull h[MAXN],p[MAXN],b=131;
char s[MAXN];
int n,pri[MAXN],g[MAXN],tot,m;
int f[MAXN];
void Euler() {
    for(int i=2; i<=n; i++) {
        if(!g[i]) {
            pri[++tot]=i;
            g[i]=i;
        }
        for(int j=1; j<=tot; j++) {
            if(pri[j]>g[i]||pri[j]>n/i) break;
            g[pri[j]*i]=pri[j];
        }
    }
}
ull hsh(int l,int r) {return h[r]-h[l-1]*p[r-l+1];}
int main() {
    scanf("%d%s",&n,s+1);
    Euler();
    p[0]=1;
    for(int i=1; i<=n; i++) p[i]=p[i-1]*b;
    for(int i=1; i<=n; i++) h[i]=h[i-1]*b+s[i];
    scanf("%d",&m);
    for(int i=1,l,r,len,res; i<=m; i++) {
        scanf("%d%d",&l,&r);
        len=r-l+1; res=0;
        while(len>1) {
            f[++res]=g[len];
            len=len/g[len];
        }
        len=r-l+1;
        for(int i=1,t; i<=res; i++) {
            t=len/f[i];
            if(hsh(l,r-t)==hsh(l+t,r))
                len=t;
        }
        printf("%d\n",len);
    }
    return 0;
}

练习2：POI 2010 Antisymmetry

题意要点：求最长回文子串。
正着哈希还有反着哈希，可以判断是否是回文子串。
枚举中心点，然后二分答案。 注意回文串长度是奇数还是偶数（此题没有）。
时间复杂度是O(n \log n)。 

#include<algorithm>
#include<cstdio>
#include<iostream>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int MAXN=5e5;
ull base=7,p[MAXN+10],h1[MAXN+10],h2[MAXN+10];
char s[MAXN+10];
int n,a[MAXN+10];
long long ans;
ull hsh1(int l,int r) {return h1[r]-h1[l-1]*p[r-l+1];}
ull hsh2(int l,int r) {return h2[l]-h2[r+1]*p[r-l+1];}
bool valid1(int x,int w) {return hsh1(x-w,x)==hsh2(x,x+w);}
bool valid2(int x,int w) {return hsh1(x-w,x)==hsh2(x+1,x+w+1);}
ll solve(int x) {
    if(hsh1(x,x)!=hsh2(x+1,x+1)||x+1>n) return 0;
    ll l=0,r=min(x,n-x);
    while(l+1<r) {
        int mid=(l+r)/2;
        if(valid2(x,mid)) l=mid;
        else r=mid;
    }
    return l+1;
}
int main() {
    scanf("%d%s",&n,s+1);
    for(int i=1; i<=n; i++) a[i]=s[i]-'0';
    p[0]=1;
    for(int i=1; i<=n; i++) p[i]=p[i-1]*base;
    for(int i=1; i<=n; i++) h1[i]=h1[i-1]*base+a[i];
    for(int i=n; i>=1; i--) h2[i]=h2[i+1]*base+(1-a[i]);
    for(int i=1; i<=n; i++) 
        ans=ans+solve(i);
    printf("%lld\n",ans);
    return 0;
}

哈希表

设计哈希函数，一个数据求出它的哈希值，把它插入到对应哈希值的链表内。
可以查询对应哈希值的链表内是否有需要查询的值。

收集雪花

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int MOD=1e7-3,MAXN=2e6,base=13331;
int tot,nxt[MAXN+10],head[MOD+10],val[MAXN+10];
int n,ans,a[MAXN+10];
void Insert(int x) {
    int b=x%MOD;
    val[++tot]=x;
    nxt[tot]=head[b];
    head[b]=tot;
}
bool Query(int x) {
    int b=x%MOD;
    for(int i=head[b]; i; i=nxt[i]) {
        if(val[i]==x) return true;
    }
    return false;
}
void Del(int x) {
    int b=x%MOD,prev;
    if(val[head[b]]==x) head[b]=nxt[head[b]];
    for(int i=head[b]; i; i=nxt[i]) {
        if(val[i]==x) {
            nxt[prev]=nxt[i];
            break;
        }
        prev=i;
    }
}
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    for(int i=1,j=1; i<=n&&j<=n+1; ) {
        if(Query(a[j])||j==n+1) {
            ans=max(ans,j-i);
            while((Query(a[j])||j==n+1)&&i<=n) {
                Del(a[i]);
                i++;
            }
        }
        Insert(a[j]); j++;
    }
    printf("%d\n",ans);
    return 0;
}