题目描述
给定一个M行N列的01矩阵(只包含数字0或1的矩阵),再执行Q次询问,每次询问给出一个A行B列的01矩阵,求该矩阵是否在原矩阵中出现过。
样例
输入样例:
3 3 2 2
111
000
111
3
11
00
11
11
00
11
输出样例:
1
0
1
算法1
(字符串hash)
主要想法:对需要判断的大小的矩阵,进行字符串hash。(比如需要在4x4的矩阵里是否存在3x3的相同的矩阵)
可以对4x4的矩阵 进行3x3的字符串hash。
二维字符串hash,可以看成如下图。
1.按列(先卡住列),对每一行进行字符串hash(记为calc
函数),记为s。
2.当增加了一行,并且$行数<= a$,在原有的$s$上, s = s * p[b] + calc(hashv[j], l, r)
,其中s * p[b]
相当于把第一行hash抬了一格子,再加上当前这行的hash值calc(hashv[j], l, r)
如图,图中是以3x3格子为例子
3.再当前扫描的矩阵行数>= a的时候需要将最上面那一行减去。注意: -calc(hashv[j - a], l, r) * p[a * b]
,*p[a * b]
的原因如图,需要将原来的hash值0, 1, 2抬成9, 10, 11。
4.再插入到set
的时候,需要判断行数>=a
满足要求再插入到set
中。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;
typedef unsigned long long ULL;
const int N = 1010, M = N * N, P = 131;
int n, m, a, b;
ULL hashv[N][N], p[M];
char str[N];
ULL calc(ULL f[], int l, int r){
return f[r] - f[l - 1] * p[r - l + 1];
}
int main(){
scanf("%d%d%d%d", &n, &m, &a, &b);
p[0] = 1;
for (int i = 1; i <= n * m; i ++) p[i] = p[i - 1] * P;
//对整个矩阵计算hash值
for (int i = 1; i <= n; i ++){
scanf("%s", str + 1);
for (int j = 1; j <= m; j ++) hashv[i][j] = hashv[i][j - 1] * P + str[j] - '0';
}
//计算出符合要求的a * b的矩阵,插入到set中,方便查询。
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);// 每一行计算,都需要把上一行hash值往上抬,再加上当前行的hash值
if (j - a > 0) s -= calc(hashv[j - a], l, r) * p[a * b]; //如果多出来的需要减掉。
if (j >= a) S.insert(s);//插入到set中,方便查询。
}
}
int Q;
scanf("%d", &Q);
while (Q --){
ULL s = 0;
for (int i = 0; i < a; i ++){
scanf("%s", str);
for (int j = 0; j < b; j ++) s = s * P + str[j] - '0';
}
if (S.count(s)) puts("1");
else puts("0");
}
return 0;
}
目前感觉最好的
好