JZTXT

哈希

发布时间 2023-06-04 22:48:27作者: TKXZ133

字符串哈希

字符串哈希是一种将字符串映射为整数的函数，可以方便地帮助判断两个字符串是否相等，或者查找字符串中的子串。

字符串哈希有多种构造方法，例如多项式哈希，双哈希，自然溢出哈希等。字符串哈希的用途很广泛，例如字符串匹配，最长回文子串，最长公共子串，确定字符串中不同子串的数量等。

字符串哈希的基本思想是将每个字符对应一个数字，然后按照一定的规则将这些数字组合成一个整数，这个整数就是字符串的哈希值。

不同的字符串可能会有相同的哈希值，这种情况称为哈希碰撞，我们希望尽量减少这种情况的发生，所以一般会选择合适的基数和模数来构造哈希函数。

如果两个字符串发生了哈希碰撞，会导致我们无法区分这两个字符串。

为了避免哈希碰撞，我们需要选择合适的基数和模数，使得哈希函数尽量是一个单射，即不同的字符串对应不同的哈希值。一般来说，基数和模数越大，哈希碰撞的概率越小，但是也会增加计算的复杂度和空间占用。

const int P1=131,P2=137;
const int mod1=1000000007,mod2=1000000009;
#define Ull unsigned long long 
const int N=100100;
#define Puu pair<Ull,Ull> 

Ull p1[N],p2[N];

struct Hash{
    Ull h1[N],h2[N];
};

void init(int n){
    p1[0]=p2[0]=1;
    for(int i=1;i<=n;i++) p1[i]=p1[i-1]*P1%mod1;
    for(int i=1;i<=n;i++) p2[i]=p2[i-1]*P2%mod2;
}

Hash calc(char s[N]){
    int n=strlen(s+1);
    Hash res;
    res.h1[0]=res.h2[0]=1;
    for(int i=1;i<=n;i++){
        res.h1[i]=(res.h1[i-1]*P1+s[i]-'0')%mod1;
        res.h2[i]=(res.h2[i-1]*P2+s[i]-'0')%mod2;
    }
    return res;
}

Puu get(Hash a,int l,int r){
    return {a.h1[r]-a.h1[l-1]*p1[r-l+1],a.h2[r]-a.h2[l-1]*p2[r-l+1]};
}

二维哈希

二维哈希将问题从一维变成二维，所有一维的问题都有对应的二维版本。

它是一种将二维数组或矩阵映射为一个唯一的数值的方法，可以用于快速比较和查询子矩阵。其基本思想是先对每一行进行一维哈希，然后再对每一列进行一维哈希，得到整个矩阵的哈希值。

查询操作利用二维前缀和的方法，减去重复的部分并乘上相应的进制数。

可以用不同的进制数和模数来减少冲突的概率。

其题目类型较一维哈希而言丰富许多，难度有所提升。

如下，统计矩阵中有多少个上下对称且左右对称的正方形，时间复杂度 \(O(n^2\log n)\)。

#include <bits/stdc++.h>
using namespace std;
const int N=2010;
#define int unsigned long long
const int P1=133,P2=233;

int a[N][N],Hash[N][N];
int p1[N],p2[N];
int ans=0,n,m;

int get(int x1,int y1,int x2,int y2){
    int Px=p2[x2-x1+1],Py=p1[y2-y1+1];
    return Hash[x2][y2]-Hash[x1-1][y2]*Px-Hash[x2][y1-1]*Py+Hash[x1-1][y1-1]*Px*Py;
}

bool check(int x1,int y1,int x2,int y2){
    if(x2<x1||y2<y1) return 0; 
    bool f1=get(x1,y1,x2,y2)==get(2*n-x2+1,y1,2*n-x1+1,y2);
    bool f2=get(x1,y1,x2,y2)==get(x1,2*m-y2+1,x2,2*m-y1+1);
    return (f1&&f2);
}

bool judge(int i,int j,int mid,int f){
    bool f1=(i-mid+f>=1&&j-mid+f>=1&&i+mid<=n&&j+mid<=m);
    if(!f1) return 0;
    bool f2=check(i-mid+f,j-mid+f,i+mid,j+mid);
    if(!f2) return 0;
    return 1;
}

signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%lld",&a[i][j]);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            a[i+n][j]=a[n-i+1][j];
            a[i][j+m]=a[i][m-j+1];
        }

    p1[0]=p2[0]=1;
    for(int i=1;i<=2*m;i++) p1[i]=p1[i-1]*P1;
    for(int i=1;i<=2*n;i++) p2[i]=p2[i-1]*P2;
    for(int i=1;i<=2*n;i++)
        for(int j=1;j<=2*m;j++)
            Hash[i][j]=Hash[i][j-1]*P1+a[i][j];
    for(int i=1;i<=2*n;i++)
        for(int j=1;j<=2*m;j++)
            Hash[i][j]+=Hash[i-1][j]*P2;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int l=0,r=max(n,m);
            while(l<r){
                int mid=(l+r+1)>>1;
                if(judge(i,j,mid,0)) l=mid;
                else r=mid-1;
            }
            ans+=l+1;

            l=0,r=max(n,m);
            while(l<r){
                int mid=(l+r+1)>>1;
                if(judge(i,j,mid,1)) l=mid;
                else r=mid-1;
            }
            ans+=l;
        }

    cout<<ans<<'\n';

    return 0;
}

树哈希

树哈希是一种对树结构进行哈希的方法，可以用来判断两棵树是否同构。

树哈希的基本思想是，以某个结点为根的子树的哈希值，就是以它的所有儿子为根的子树的哈希值构成的多重集的哈希。

有很多种不同的哈希函数可以选择，比如乘上质数、进制哈希、异或哈希等。树哈希可以用来解决一些树同构、括号序列等问题。

树哈希的优点是可以快速地判断两棵树是否同构，降低复杂度，而且实现起来比较简单。

树哈希的缺点是可能会出现哈希冲突，即两棵不同构的树有相同的哈希值，导致误判。另外，树哈希也需要选择合适的哈希函数和参数，以避免被卡常或者被出题人针对。

数据结构维护哈希

在某些情况下，需要对哈希数组进行一些奇怪的操作，如求最值，求和，修改，插入等，这时就可以用数据结构对其进行维护。

维护时，需要将左右子区间的哈希值合并。

维护方式包括线段树，平衡树，树状数组等等。