# 题意
给定一个n行m列的矩阵（矩阵中只包含数字0或1）
执行q次询问，每次给出一个n行m列的矩阵，
问矩阵是否在原矩阵中出现过
# 题解
1） 将矩阵用字符串读入，将矩阵每一行的hash值求出来
2） 按列来进行枚举，从第b列开始，即当前的列数一定大于b列，然后左边就是当前列-b+1，一行一行的进行扩展，如果当前行数大于a则把当前-a的行即固定矩形的上一行减去，只有行数大于a的时候才会满足是可能的a*b的矩形
3） 每次满足询问矩阵大小就加入hash表
4） unordered_map存储如果已经存在就证明有
1 #include <bits/stdc++.h> 2 #define ull unsigned long long 3 using namespace std; 4 const int N=1010,P=131; 5 ull p[N*N],h[N][N]; 6 int n,m,a,b; 7 char str[N]; 8 ull get(ull f[], int l, int r) 9 { 10 return f[r] - f[l - 1] * p[r - l + 1]; 11 } 12 int main(){ 13 cin>>n>>m>>a>>b; 14 p[0] = 1; 15 for (int i = 1; i <= n * m; i ++ ) p[i] = p[i - 1] * P; 16 17 for (int i = 1; i <= n; i ++ ) 18 { 19 scanf("%s", str + 1); 20 for (int j = 1; j <= m; j ++ ) h[i][j] = h[i][j - 1] * P + str[j] - '0'; 21 } 22 unordered_map<ull,int> f; 23 for (int i = b; i <= m; i ++ ) 24 { 25 ull s = 0; 26 int l = i - b + 1, r = i; 27 for (int j = 1; j <= n; j ++ ) 28 { 29 s = s * p[b] + get(h[j], l, r); 30 if (j - a > 0) s -= get(h[j - a], l, r) * p[a * b]; 31 if (j >= a) f[s]++; 32 } 33 } 34 int Q; 35 scanf("%d", &Q); 36 while (Q -- ) 37 { 38 ull s = 0; 39 for (int i = 0; i < a; i ++ ) 40 { 41 scanf("%s", str); 42 for (int j = 0; j < b; j ++ ) s = s * P + str[j] - '0'; 43 } 44 if (f[s]) puts("1"); 45 else puts("0"); 46 } 47 return 0; 48 }
原文链接: https://www.cnblogs.com/hhyx/p/12514891.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/374330
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
