矩阵

题目 矩阵

思路分析

分析子矩阵是否在大矩阵中出现过 本来是要一个元素一个元素比对的

显然太麻烦了

借鉴字符串哈希的思路

把矩阵也哈希成一个值 判断某个矩阵是否出现过 只要看这个值是否在预处理set里面

（要查a*b的矩形是否出现 把原矩阵里所有的a*b的矩形都哈希处理出来 存在set里）

和直接二维前缀和不太一样 这里也是使用二维单调队列的那个优化方式

先处理好每一行的哈希值的前缀和 这样就可以很容易计算出某个区间（固定宽）的前缀和

然后再按列来做 在固定宽的基础上 算出每一个矩形的前缀和

当高度到了a时 我们要的a*b就形成了

再加一行的话 就得把最上面一行的值给减掉去

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

const int N=1010,M=N*N,P=131;

ULL hashv[N][N],p[M];

char str[N];

int n,m,a,b;

ULL calc(ULL f[],int l,int r)

{

    return f[r]-f[l-1]*p[r-l+1];

}

int main()

{

    cin>>n>>m>>a>>b;

    p[0]=1;

    for(int i=1;i<=n*m;i++)

        p[i]=p[i-1]*P;

    for(int i=1;i<=n;i++){

        cin>>str+1;

        for(int j=1;j<=m;j++)

            hashv[i][j]=hashv[i][j-1]*P+str[j];

    }

    unordered_set<ULL> S;

    for(int i=b;i<=m;i++){

        ULL s=0;

        int l=i-b+1,r=i;//固定窗口大小

        for(int j=1;j<=n;j++){//枚举每一列

            s=s*p[b]+calc(hashv[j],l,r);//上一行的值左移 加上这一行的值 为当前矩阵的值

            if(j-a>0)//矩形形成 删去上面的一行

                s-=calc(hashv[j-a],l,r)*p[a*b];

            if(j>=a)//该矩形的哈希加入set

                S.insert(s);

        }

    }

    int Q;

    cin>>Q;

    while(Q--){

        ULL s=0;

        for(int i=0;i<a;i++){

            cin>>str;

            for(int j=0;j<b;j++)

                s=s*P+str[j];

        }

        if(S.count(s))

            cout<<1<<endl;

        else

            cout<<0<<endl;

    }

    return 0;

}

同类题型

视频讲解

⬅️ 回文串的最大长度 🏠 00-刷题理模型 ➡️ 最小表示法