二维哈希

要求在预处理后，能用O(1)的时间得到矩阵内任何矩形区域的哈希值
例题goto

思路

类似于二维前缀和，预处理出F[i,j]表示前1-i行i-j列展开的哈希值，预处理时，建议用两个不同的质数作为权值，一个处理行上的，一个处理列上的，两个过程可以分开进行

ULL hasha[n+1][m+1];
for (int i=1;i<=n;++i){
    for (int j=1;j<=m;++j){
        hasha[i][j]+=hasha[i][j-1]*pi;
    }
}
for (int i=1;i<=n;++i){
    for (int j=1;j<=m;++j){
        hasha[i][j]+=hasha[i-1][j]*pj;
    }
}

想要获得其中一块区域的哈希值时，用类似于二维前缀和的方式，下面是获取以i,j为右下角，长宽分别为a，b的区域的哈希值

p1[1]=pi;
p2[1]=pj;
for (int i=2;i<=a;++i) p2[i]=p2[i-1]*pj;
for (int i=2;i<=b;++i) p1[i]=p1[i-1]*pi;

ULL tmp=hasha[i][j]-hasha[i-a][j]*p2[a]-hasha[i][j-b]*p1[b]+hasha[i-a][j-b]*p2[a]*p1[b];  //注意P1，P2不要搞错

下面是原题代码，无奈开O3优化

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
#pragma GCC optimize (3)
#pragma G++ optimize (3)
ULL pi=131,pj=13331,p1[1005],p2[1005],hasha[1005][1005],hashb[1005][1005],ans[1000005],cnt;
int n,m,a,b;

void init(){
    p1[1]=pi;
    p2[1]=pj;
    for (int i=2;i<=a;++i) p2[i]=p2[i-1]*pj;
    for (int i=2;i<=b;++i) p1[i]=p1[i-1]*pi;
}

int main(){
    cin>>n>>m>>a>>b;
    init();
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            scanf("%1llu",&hasha[i][j]);
        }
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            hasha[i][j]+=hasha[i][j-1]*pi;
        }
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            hasha[i][j]+=hasha[i-1][j]*pj;
        }
    }
    for (int i=a;i<=n;++i){
        for (int j=b;j<=m;++j){
            ULL tmp=hasha[i][j];
            tmp-=hasha[i-a][j]*p2[a];
            tmp-=hasha[i][j-b]*p1[b];
            tmp+=hasha[i-a][j-b]*p2[a]*p1[b];
            ans[++cnt]=tmp;
        }
    }
    int t;
    cin>>t;
    while (t--){
        for (int i=1;i<=a;++i){
            for (int j=1;j<=b;++j){
                scanf("%1llu",&hashb[i][j]);
            }
        }
        for (int i=1;i<=a;++i){
            for (int j=1;j<=b;++j){
                hashb[i][j]+=hashb[i][j-1]*pi;
            }
        }
        for (int i=1;i<=a;++i){
            for (int j=1;j<=b;++j){
                hashb[i][j]+=hashb[i-1][j]*pj;
            }
        }
        int y=0;
        ULL tmp=hashb[a][b];
        for (int i=1;i<=cnt;++i){
            if (ans[i]==tmp){
                puts("1");
                y=1;
                break;
            }
        }
        if (!y) puts("0");
    }
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/98/