哈希学习笔记

hash学习笔记

常用函数: $ hash[i] = sum _{j=i} ^{len-1} {s[j]*X^{j-i}}, X ≥ |字符集| $ 取多个模，对于一个子串(s[i]s[i+1]..s[j])的(hash = hash[i] - hash[j+1]*X^{j-i+1})，预处理(hash[i])以及(X^i)即可(O(1))求出所有的子串hash值
一般运用hash进行快速查找，状态压缩，其他hash相关：康托展开及逆展开，ELFhash

Problem A

题意：给定一字符串S，询问(LCP(x,y))，即从x,y分别开始的最长公共前缀
做法：二分最长公共前缀的长度L，(O(1))判断两个串的(hash)是否相同

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define frep(i,a,b) for(int i=a;i>=b;--i)
typedef unsigned long long ll;
const int N = 100007;
const ll base = 107;
using namespace std;
int n,q;
ll P[11][N], h[11][N], mod[11];
int cc;
char s[N];
void init_hash() {
    cc=0;
    mod[++cc] = 1e9+7;
    mod[++cc] = 1000007;
    mod[++cc] = 998244353;
    mod[++cc] = 100007;

    P[0][0]=1; rep(i,1,100) P[0][i]=P[0][i-1]*base;
    frep(i,n,1) h[0][i] = h[0][i+1]*base + s[i];

    rep(i,1,cc){
        P[i][0]=1;
        rep(j,1,100) P[i][j]=(P[i][j-1]*base)%mod[i];
    }
    rep(i,1,cc)frep(j,n,1)h[i][j] = ((h[i][j+1]*base)%mod[i]+s[j])%mod[i];
}
ll ask0(int x,int y) {
    if(x>y)swap(x,y);
    return h[0][x]-h[0][y+1]*P[0][y-x+1];
}
ll ask1(int x,int y,int z) {
    if(x>y)swap(x,y);
    return (h[z][x]%mod[z]-(h[z][y+1]*P[z][y-x+1])%mod[z]+mod[z])%mod[z];
}
int ck(int x,int y,int L) {
    if(ask0(x,x+L-1)!=ask0(y,y+L-1))return 0;
    rep(i,1,cc){
        if(ask1(x,x+L-1,i)!=ask1(y,y+L-1,i)) return 0;
    }
    return 1;
}
int solve(int x,int y) {
    int l=1,r=min(n-x+1,n-y+1),mid,ans=0;
    if(s[x]!=s[y])return 0;
    while(l<=r) {
        mid = (l+r)>>1;
        if(ck(x,y,mid))l=mid+1,ans=mid;
        else r=mid-1;
    }
    return ans;
}

int main() {
    scanf(" %s",s+1);
    n=strlen(s+1);
    init_hash();
    scanf("%d",&q);
    while(q--) {int x,y;
        scanf("%d %d",&x,&y);
        printf("%d
",solve(x,y));
    }
    return 0;
}

Problem B

题意：给定一字符串S，1）询问(LCP(x,y))，即从x,y分别开始的最长公共前缀；2）修改位置x的字符为y
做法1：线段树维护维护每个位置的hash[i]，修改操作相当于给区间[1,x]加上

[(y-s[x])*X^x,(y-s[x])*X^x-1,...(y-s[x])*X^0 ]

这一等比数列，查询就是单点查询，再用上一题的做法即可。区间加公比固定的等比数列
3. 做法2：线段树维护(S[i]*X^i)修改就是单点修改，查询([i,j])区间和之后要除以(X^i),要预处理对应模数的逆元。代码回头补。

Problem C [BZOJ1014]

题意：给定一字符串S，1）询问(LCP(x,y))，即从x,y分别开始的最长公共前缀；2）修改位置x的字符为y；3）在S的第x个字符后添加一个字符
做法：splay每个节点维护size[i]：子树大小，hash[i]：以i为根节点的子树的hash值，(hash[fa]=hash[lson]+s[fa]*X^{size[lson]}+hash[rson]*X^{size[lson]+1})，对于查询，每次把一个后缀旋转到一颗子树上，子树的根节点的hash值就是答案，对于修改，直接修改从这个点到根的路径上的hash值，对于插入，直接splay插入更新size和hash。代码等到学splay专题的时候我再努力写吧。

Problem D [BZOJ3555]

题意：n个长度为L的互不相同的字符串，求有多少对字符串互相相似。相似：如果两个字符串恰好有一个字符不同，则他们相似。n≤30000，L≤200，|字符集|≤64
做法：预处理每个串前缀的hash值，枚举哪一位不同，排序计算贡献。关键是如何快速求出去除第i位的字符串的hash值。下面进行推导：
对于字符串S, (hash[i] = S[1]*X^{i-1} + S[2]*X^{i-2} + ... + S[i])
除去S串的第(x)个字符的字符串(Hash = (S[1]*X^{n-1} + S[2]*X^{n-2} + ... + S[x-1]*X^{n-x+1})+(S[x+1]*X^{n-x}+S[x+2]*X^{n-x-1}...+S[n])\= hash[x-1]*X^{n-x+1} +(hash[n]-hash[x]*X^{n-x}))

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define frep(i,a,b) for(int i=a;i>=b;--i)
typedef unsigned long long ll;
const int N = 50100;
const ll base = 107;
using namespace std;
int n,q,L,X;
ll P[211], h[N][211],a[N];
char s[211];
ll cal(int s,int x) {
    return h[s][x-1]*P[L-x+1] +(h[s][L]-h[s][x]*P[L-x]);
}
int main() {
    scanf("%d%d%d",&n,&L,&X);
    P[0]=1;rep(i,1,L)P[i]=P[i-1]*base;
    rep(i,1,n) {
        scanf(" %s",s+1);
        rep(j,1,L) h[i][j]=h[i][j-1]*base+s[j];
    }
    int ans=0;
    rep(i,1,L){
        rep(j,1,n)a[j]=cal(j,i);
        sort(a+1,a+n+1);
        int tmp = 0;
        rep(j,2,n){
            if(a[j]!=a[j-1])tmp=0;
            else ++tmp;
            ans += tmp;
        }
    }
    printf("%d
",ans);
    return 0;
}

二维hash[BZOJ2462]

题意：给定一个M行N列的01矩阵，以及Q个A行B列的01矩阵，你需要求出这Q个矩阵哪些在
原矩阵中出现过。所谓01矩阵，就是矩阵中所有元素不是0就是1。
做法：类似一维hash，先竖着hash，再横着hash，两次要用不同的base，查询子矩形方法类似于差分。
hints：本题要对矩阵的hash值二次取mod，用map会tle

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
typedef unsigned long long ll;
const int N = 1007;
const ll base1 = 107;
const ll base2 = 31;
const ll mod = 10000007;
using namespace std;
int n,m,a,b,q;
ll P1[N], P2[N], h[N][N];
bool vis[mod+1];
char mp[N][N];
void init_hash() {
    P1[0]=1; rep(i,1,100) P1[i]=P1[i-1]*base1;
    P2[0]=1; rep(i,1,100) P2[i]=P2[i-1]*base2;
    rep(i,1,n)rep(j,1,m) h[i][j] += h[i-1][j]*base1 + mp[i][j];
    rep(i,1,n)rep(j,1,m) h[i][j] += h[i][j-1]*base2;
}
ll ask(int x,int y,int xl,int yl) {
    return h[x][y]-h[x-xl][y]*P1[xl]-h[x][y-yl]*P2[yl]+h[x-xl][y-yl]*P1[xl]*P2[yl];
}
int main() {
    scanf("%d%d%d%d",&n,&m,&a,&b);
    rep(i,1,n)scanf(" %s",mp[i]+1);
    init_hash();
    rep(i,a,n)rep(j,b,m) vis[ask(i,j,a,b)%mod]=1;
    scanf("%d",&q);
    while(q--) {
        rep(i,1,a)scanf(" %s",mp[i]+1);
        memset(h,0,sizeof(h));
        rep(i,1,a)rep(j,1,b)h[i][j]+=h[i-1][j]*base1+mp[i][j];
        rep(i,1,a)rep(j,1,b)h[i][j]+=h[i][j-1]*base2;
        printf("%d
",vis[h[a][b]%mod]);
    }
    return 0;
}