Bzoj 2351(二维Hash)

BZOJ 2351
题意:给定$n \times m$大小矩阵,$q$次询问$a \times b$大小矩阵是否是大矩阵的一部分。

给行列分别hash一次,行先hash,然后将hash值再hash一次,即hash列

然后查询子矩阵Hash值直接像二维前缀和一样做即可,类比于一维的 Hash 方法

知识点:
1、二维Hash
2、Hash值选取
3、Hash的方法取决于是否会冲突,这里运用不同模数巧妙解决冲突

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
#include<vector>
#include<utility>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
int m, n, a, b, q;
unsigned LL bs1 = 257, bs2 = 259, hsh[1005][1005], p1[1005], p2[1005], whw[1005][1005];
map<unsigned LL, bool > ma;
void clean() {
ms(whw, 0), ms(hsh, 0);
}
int solve() {
clean();
scanf("%d%d%d%d", &m, &n, &a, &b);
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) scanf("%1lld", &hsh[i][j]), ++hsh[i][j];
scanf("%d", &q);
if (m < a || n < b) {
while (q--) printf("0\n");
return 0;
}
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) hsh[i][j] += hsh[i - 1][j] * bs1;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) hsh[i][j] += hsh[i][j - 1] * bs2;
p1[0] = p2[0] = 1;
for (int i = 1; i <= 1000; ++i) p1[i] = p1[i - 1] * bs1;
for (int i = 1; i <= 1000; ++i) p2[i] = p2[i - 1] * bs2;
for (int i = a; i <= m; ++i)
for (int j = b; j <= n; ++j) ma[hsh[i][j] - hsh[i - a][j] * p1[a] - hsh[i][j - b] * p2[b] + hsh[i - a][j - b] * p1[a] * p2[b]] = true;
while (q--) {
for (int i = 1; i <= a; ++i)
for (int j = 1; j <= b; ++j) scanf("%1lld", &whw[i][j]), ++whw[i][j];
for (int i = 1; i <= a; ++i)
for (int j = 1; j <= b; ++j) whw[i][j] += whw[i - 1][j] * bs1;
for (int i = 1; i <= a; ++i)
for (int j = 1; j <= b; ++j) whw[i][j] += whw[i][j - 1] * bs2;
map<unsigned LL, bool >::iterator it = ma.find(whw[a][b]);
if (it != ma.end()) {
if (it->second == true) printf("1\n"); else printf("0\n");
} else printf("0\n");
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------