矩陣
給定一個M行N列的01矩陣（只包含數字0或1的矩陣），再執行Q次詢問，每次詢問給出一個A行B列的01矩陣，求該矩陣是否在原矩陣中出現過，
輸入格式
第一行四個整數M,N,A,B，
接下來一個M行N列的01矩陣，數字之間沒有空格，
接下來一個整數Q，
接下來Q個A行B列的01矩陣，數字之間沒有空格，
輸出格式
對于每個詢問，輸出1表示出現過，0表示沒有出現過，
資料范圍
A≤100，M,N,B≤1000，Q≤1000
輸入樣例：
3 3 2 2
111
000
111
3
11
00
11
11
00
11
輸出樣例
1
0
1
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
using namespace std;
typedef unsigned long long ULL;
const int N = 1010, M = N * N, P = 131;
char str[N];
ULL f[N][N], p[M];
int n, m, a, b;
// 求區間 hash 值
ULL get(ULL f[], int l, int r) {
return f[r] - f[l - 1] * p[r - l + 1];
}
int main() {
cin >> n >> m >> a >> b;
// 求取 P 進制陣列
p[0] = 1;
for (int i = 1; i <= m * n; i ++) p[i] = p[i - 1] * P;
for (int i = 1; i <= n; i ++) {
scanf("%s", str + 1);
// 預先將每一行 hash 化
for (int j = 1; j <= m; j ++) f[i][j] = f[i][j - 1] * P + str[j] - '0';
}
// 列舉每一個 a * b 的矩陣，將 hash 值填入 set 中
unordered_set<ULL> hash;
for (int i = b; i <= m; i ++) {
ULL s = 0;
int l = i - b + 1, r = i;
for (int j = 1; j <= n; j ++) {
// 獲取以當前行的結尾矩陣 hash 值
s = s * p[b] + get(f[j], l, r);
// 將當前行的 hash 值 - 第一行的 hash 值
if (j > a) s -= get(f[j - a], l, r) * p[a * b];
// 將該矩陣的 hash 值放入 set
if (j >= a) hash.insert(s);
}
}
int k;
cin >> k;
while (k --) {
ULL s = 0;
for (int i = 0; i < a; i ++) {
scanf("%s", str);
// 求出當前行的 hash 值
for (int j = 0; j < b; j ++) s = s * P + str[j] - '0';
}
// 判斷 set 中是否存在該矩陣
if (hash.count(s)) puts("1");
else puts("0");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/252126.html
標籤：其他
下一篇：《圖解TCP/IP》筆記