做这题之前首先需要先了解一下二维的 Hash
二维的 Hash 其实就是先对一行的每列元素进行一次 hash, 处理完之后. 再对每一行的元素进行 hash
查询的时候有点类似二维的前缀和:
题目链接: https://vjudge.net/contest/344930#problem/H
题目大意: 让你在一个大小为???? 的矩阵中找大小是???? 的矩阵的出现次数
思路: 就是一个裸的二维 Hash
- #include <stdio.h>
- #include <algorithm>
- #include <iostream>
- #include <stdlib.h>
- #include <string>
- #include <string.h>
- #include <math.h>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <map>
- #include <set>
- #define INF 0x3f3f3f3f
- #define LL long long
- typedef unsigned long long ull;
- const int maxn = 1e3+10;
- char a[maxn][maxn],b[maxn][maxn];
- ull base1 = 233,base2 = 2333;
- ull ha[maxn][maxn],hb[maxn][maxn];
- int main() {
- int T;
- scanf("%d",&T);
- while (T--) {
- int n,m,x,y;
- scanf("%d%d",&n,&m);
- for (int i=1;i<=n;i++) {
- scanf("%s",a[i]+1);
- }
- scanf("%d%d",&x,&y);
- for (int i=1;i<=x;i++) {
- scanf("%s",b[i]+1);
- }
- ull p1 = 1,p2 = 1;
- for (int i=1;i<=x;i++) {
- p2 *= base2;
- }
- for (int i=1;i<=y;i++) {
- p1 *= base1;
- }
- for (int i=1;i<=x;i++) {
- for (int j=1;j<=y;j++) {
- hb[i][j] = (b[i][j] - 'a') + hb[i][j-1] * base1 + hb[i-1][j] * base2 - hb[i-1][j-1] * base1 * base2;
- }
- }
- int ans = 0;
- for (int i=1;i<=n;i++) {
- for (int j=1;j<=m;j++) {
- ha[i][j] = (a[i][j] - 'a') + ha[i][j-1] * base1 + ha[i-1][j] * base2 - ha[i-1][j-1] * base1 * base2;
- if (i>= x && j>= y && hb[x][y] == ha[i][j] - ha[i-x][j] * p2 - ha[i][j-y] * p1 + ha[i-x][j-y] * p1 * p2) {
- ans++;
- }
- }
- }
- printf("%d\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3307984.html