牛客-Matrix(二维Hash-矩阵匹配)
题目链接:https://ac.nowcoder.com/acm/problem/51003
题目描述
给定一个M行N列的01矩阵(只包含数字0或1的矩阵),再执行Q次询问,每次询问给出一个A行B列的01矩阵,求该矩阵是否在原矩阵中出现过。
输入描述:
第一行四个整数M,N,A,B。
接下来一个M行N列的01矩阵,数字之间没有空格。
接下来一个整数Q。
接下来Q个A行B列的01矩阵,数字之间没有空格。
输出描述:
对于每个询问,输出1表示出现过,0表示没有。
输入
3 3 2 2
111
000
111
3
11
00
11
11
00
11
输出
1
0
1
备注:
对于40%的数据,A = 1。
对于80%的数据,A≤10。
对于100%的数据,A≤100,M,N≤1000,Q≤1000。
emmm,就是个二维Hash的板子题,我们先对每行的前缀维护一下Hash值,最对每列维护每行前缀的前缀值。其维护过程如下:(nm这是真的难受,缩进太大了,每次要手动搞一下QAQ)
void get_hash(int n,int m,int type)
{
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
if (type) hashs[i][j]=hashs[i][j-1]*base1+s[i][j];
else sub_hash[i][j]=sub_hash[i][j-1]*base1+s[i][j];
for (int j=1; j<=m; j++)
for (int i=1; i<=n; i++)
if (type) hashs[i][j]=hashs[i-1][j]*base2+hashs[i][j];
else sub_hash[i][j]=sub_hash[i-1][j]*base2+sub_hash[i][j];
}
然后我们将模板矩阵的每个A行B列的子矩阵的Hash值算出来,这里有点类似于前缀和的:
for (int i=a; i<=n; i++)
for (int j=b; j<=m; j++) {
ull sb=hashs[i][j]-hashs[i-a][j]*pw2[a]-hashs[i][j-b]*pw1[b]+hashs[i-a][j-b]*pw2[a]*pw1[b];
mos[++cnt]=sb;
}
以下是AC代码:
#include <bits/stdc++.h>
using namespace std;
const int mac=1e3+10;
const int base1=131,base2=137;
typedef unsigned long long ull;
char s[mac][mac];
ull hashs[mac][mac],mos[mac*mac],sub_hash[120][mac];
ull pw1[mac],pw2[mac];
void get_hash(int n,int m,int type)
{
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
if (type) hashs[i][j]=hashs[i][j-1]*base1+s[i][j];
else sub_hash[i][j]=sub_hash[i][j-1]*base1+s[i][j];
for (int j=1; j<=m; j++)
for (int i=1; i<=n; i++)
if (type) hashs[i][j]=hashs[i-1][j]*base2+hashs[i][j];
else sub_hash[i][j]=sub_hash[i-1][j]*base2+sub_hash[i][j];
}
int main(int argc, char const *argv[])
{
int n,m,a,b;
scanf ("%d%d%d%d",&n,&m,&a,&b);
for (int i=1; i<=n; i++)
scanf ("%s",s[i]+1);
get_hash(n,m,1);
int cnt=0;
pw1[0]=pw2[0]=1;
for (int i=1; i<=max(n,m); i++) pw1[i]=pw1[i-1]*base1,pw2[i]=pw2[i-1]*base2;
for (int i=a; i<=n; i++){
for (int j=b; j<=m; j++){
ull sb=hashs[i][j]-hashs[i-a][j]*pw2[a]-hashs[i][j-b]*pw1[b]+hashs[i-a][j-b]*pw2[a]*pw1[b];
mos[++cnt]=sb;
}
}
sort(mos+1,mos+cnt+1);
int q;
scanf ("%d",&q);
while (q--){
for (int i=1; i<=a; i++)
scanf ("%s",s[i]+1);
get_hash(a,b,0);
int flag=0;
int pos=lower_bound(mos+1,mos+1+cnt,sub_hash[a][b])-mos-1;
if (pos<cnt && mos[pos+1]==sub_hash[a][b]) flag=1;
if (flag) printf("1
");
else printf("0
");
}
return 0;
}