柒葉灬 的博客

柒葉灬 的博客

hash总结(个人笔记)

posted on 2018-12-27 22:23:22 | under 专题总结 |

$hash$ 专题总结


$Hash$ 不用过多讲了,就是将状态映射成一个数字,其中数字本质上就是 $K$ 进制数, $K≥$ 状态数 。


$hash$ 需要一个 $base$ (与进制),和一个模数 $P$ (拼人品),其中 $base$ 必须要大于等于状态数。不然如果发生了进位那么就没有意义了。

还是例题更能说明问题


例题 专题A

题意:给三个字符串,问是否存在一个字符串,满足同时是三个字符串的子串,如果有则输出最长长度,否则输出 $0$ 。

思路:先要二分,因为显然满足带调性,接下来就是 $hash$ 了,把第一个字符串所有长度为 $K$ 的放进 $set$ 里面,然后...(略)

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5,base=31,P=1e9+9;
set<int>s1,s2;
int Pow[maxn];
void init(){
    Pow[0]=1;
    for(int i=1;i<maxn;i++)
        Pow[i]=1LL*Pow[i-1]*base%P;
}
struct String{
    char str[maxn];
    int n,sum[maxn];
    int Query(int l,int r){
        return (sum[r]-1LL*sum[l-1]*Pow[r-l+1]%P+P)%P;
    }
    void read(){
        scanf("%s",str+1);
        n=strlen(str+1);
        for(int i=1;i<=n;i++)
            sum[i]=(1LL*sum[i-1]*base+str[i]-'a')%P;
    }
    void add1(int x){
        for(int i=x;i<=n;i++)
            s1.insert(Query(i-x+1,i));
    }
    void add2(int x){
        for(int i=x;i<=n;i++){
            int tmp=Query(i-x+1,i);
            if(s1.find(tmp)!=s1.end())
                s2.insert(tmp);
        }
    }
    bool find(int x){
        for(int i=x;i<=n;i++)
            if(s2.find(Query(i-x+1,i))!=s2.end())return true;
        return false;
    }
}A,B,C;
bool check(int x){
    s1.clear();s2.clear();
    A.add1(x);B.add2(x);
    return C.find(x);
}
int main(){
    init();
    int QuQ;cin>>QuQ;
    for(int cas=1;cas<=QuQ;cas++){
        A.read();B.read();C.read();
        int l=1,r=min(A.n,min(B.n,C.n)),ans=0;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)){
                ans=mid;
                l=mid+1;
            }else r=mid-1;
        }
        printf("Case %d: %d\n",cas,ans);
    }
    return 0;
}

例题 专题B

思路:因为 $2$ 个 $hash$ 的数值加起来要正好满足 $10$ 进制,所以 $base$ 必须是 $10$ ,同时枚举等号时也就可以大致确定加号位置。(个位数+个位数!=百位数)

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,ansa,ansb;
char str[maxn];
struct Hash{
    int sum[maxn],f[maxn],base,P;
    void init(int Bas,int Pi){
        base=Bas;P=Pi;
        for(int i=1;i<=n;i++)
            sum[i]=(1LL*sum[i-1]*base+str[i]-'0')%P;
        f[0]=1;
        for(int i=1;i<maxn;i++)
            f[i]=1LL*f[i-1]*base%P;
    }
    int solve(int l,int r){
        return (sum[r]-1LL*sum[l-1]*f[r-l+1]%P+P)%P;
    }
}hash1,hash2;
struct node{
    int a,b;
    void operator +=(const node &_){
        a=(a+_.a)%hash1.P;
        b=(b+_.b)%hash2.P;
    }
    bool operator ==(const node &_)const{
        return a==_.a&&b==_.b;
    }
    void solve(int l,int r){
        a=hash1.solve(l,r);
        b=hash2.solve(l,r);
    }
}tmp,A,B,C;
node check(int i,int j){
    if(i>=j||i<1||str[1]=='0'&&i>1||str[i+1]=='0'&&j>i+1)return tmp;
    A.solve(1,i);
    B.solve(i+1,j);
    A+=B;
    return A;
}
void solve(){
    tmp.a=2e9;
    tmp.b=2e9;
    for(int i=n;i>=1;i--){
        if(str[i]=='0'&&i!=n)continue;
        C.solve(i,n);
        int len=n-i+1;
        if(check(len,i-1)==C){
            ansa=len;
            ansb=i-1;
            return;
        }
        if(check(len-1,i-1)==C){
            ansa=len-1;
            ansb=i-1;
            return;
        }
        if(check(i-1-len,i-1)==C){
            ansa=i-1-len;
            ansb=i-1;
            return;
        }
        if(check(i-len,i-1)==C){
            ansa=i-len;
            ansb=i-1;
            return;
        }
    }
}
int main(){
    scanf("%s",str+1);
    n=strlen(str+1);
    hash1.init(10,1e9+13);
    hash2.init(10,1e9+9);
    solve();
    for(int i=1;i<=n;i++){
        printf("%c",str[i]);
        if(ansa==i)putchar('+');
        else if(ansb==i)putchar('=');
    }
    return 0;
}

例题 专题C

题意:输入矩阵 $A$ ,矩阵 $B$ ,问矩阵 $B$ 在 矩阵 $A$ 中出现了多少次。

思路:最重要的是怎么把一个矩阵 $hash$ 成一个值,每一个字符对应的系数应该是多少,然后怎么相减减出来。

可以造一个矩阵来说明:

$$\begin{bmatrix} 1&2&3 \\ 4&5&6\\7&8&9 \end{bmatrix}$$

数字表示对应位置的系数。

做法:先预处理横着的 $sum$ 的 $hash$ 前缀,然后按列处理即可。

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1e3+5;
int ans;
long long tot;
struct Matrix{
    int n,m;
    char mp[maxn][maxn];
    struct Hash{
        int tot,sum[maxn][maxn],f[maxn],base,P;
        void init(int Bas,int Pi,char mp[maxn][maxn],int n,int m){
            P=Pi;base=Bas;
            tot=0;
            f[0]=1;
            for(int i=1;i<maxn;i++)
                f[i]=1LL*f[i-1]*base%P;
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++)
                    sum[i][j]=(1LL*sum[i][j-1]*base+mp[i][j]-'a')%P;
                tot=(1LL*tot*f[m]+sum[i][m])%P;
            }
        }
        int solve(int row,int l,int r){
            return (sum[row][r]-1LL*sum[row][l-1]*f[r-l+1]%P+P)%P;
        }
    }hash1,hash2;
    struct node{
        int len,sum1[maxn],sum2[maxn],f1[maxn],f2[maxn];
        void init(int l,int r,int n,int h1[maxn],int h2[maxn],int Sum1[maxn][maxn],int Sum2[maxn][maxn],int P1,int P2){
            len=r-l+1;
            f1[0]=f2[0]=1;
            for(int i=1;i<=n;i++){
                f1[i]=1LL*f1[i-1]*h1[len]%P1;
                f2[i]=1LL*f2[i-1]*h2[len]%P2;
            }
            #define solve1(row,l,r) (Sum1[row][r]-1LL*Sum1[row][l-1]*h1[r-l+1]%P1+P1)%P1
            #define solve2(row,l,r) (Sum2[row][r]-1LL*Sum2[row][l-1]*h2[r-l+1]%P2+P2)%P2
            for(int i=1;i<=n;i++){
//              debug(solve1(i,l,r)); 
                sum1[i]=(1LL*sum1[i-1]*h1[len]+solve1(i,l,r))%P1;
                sum2[i]=(1LL*sum2[i-1]*h2[len]+solve2(i,l,r))%P2;
            }
        }
        long long solve(int l,int r,int P1,int P2){
            int a=(sum1[r]-1LL*sum1[l-1]*f1[r-l+1]%P1+P1)%P1;
            int b=(sum2[r]-1LL*sum2[l-1]*f2[r-l+1]%P2+P2)%P2;
            return a|b<<32;
        }
    }S;
    void read(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%s",mp[i]+1);
        hash1.init(29,1e9+7,mp,n,m);
        hash2.init(31,1e9+9,mp,n,m);
        tot=hash1.tot|hash2.tot<<32;
    }
    void check(int x,int l,int r){
        S.init(l,r,n,hash1.f,hash2.f,hash1.sum,hash2.sum,hash1.P,hash2.P);
        for(int i=1;i<=n-x+1;i++){
            if(S.solve(i,i+x-1,hash1.P,hash2.P)==tot){
                ans++;
            }
        }
    }
}A,B;
int main(){
    for(int _=(cin>>_,_);_--;){
        ans=0;
        A.read();B.read();
        for(int i=1;i<=A.m-B.m+1;i++){
            A.check(B.n,i,i+B.m-1);
        }
        printf("%d\n",ans);
    }
    return 0;
}

如果你认真看完了上面的代码,你会发现它其丑无比。

原因就是我希望弄一个双 $hash$ ,然而一个结构体里面的两个结构体不能调用函数,所以。。。

就表现出一直在引用数组的尴尬情况。

划重点:hash被卡的概率是比较低的,如果不是离线赛可以用单hash,如果错了,尝试改 $P$ 的值就行了


这是后来加的:hash的时候一定要 $+1$ !!,不然的话很容易冲突,比如说 $a$ 和 $aaa$ ,(如果不 $+1$ )他们都是0