二维哈希

前置芝士

• 哈希
• 前缀和

教程

二维哈希

板子

P10474 BeiJing2011 Matrix 矩阵哈希 - 洛谷

代码

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const ull RowBase = 131, ColBase = 1313;
const int maxn = 1005;
int n, m, a, b;
ull row[maxn], col[maxn];
ull matrix[maxn][maxn], submat[maxn][maxn];

inline void hashInit() {
    row[0] = col[0] = 1; //row:行基数，col:列基数；第 0 位初始化为 1
    for (int i = 1; i <= n; i++) { // row[i] 表示第 i 位的以 RowBase 为进制的基数
        row[i] = row[i - 1] * RowBase;
    }
    for (int i = 1; i <= m; i++) { // col[i] 表示第 i 位的以 ColBase 为进制的基数
        col[i] = col[i - 1] * ColBase;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) { // 把每一行压缩成一个 RowBase 进制数
            matrix[i][j] = matrix[i][j] + matrix[i][j - 1] * RowBase;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) { // 把每一列压缩成一个 ColBase 进制数
            matrix[i][j] = matrix[i][j] + matrix[i - 1][j] * ColBase;
        }
    }
}

inline void initSubmat() {
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            submat[i][j] = submat[i][j] + submat[i][j - 1] * RowBase;
        }
    }
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            submat[i][j] = submat[i][j] + submat[i - 1][j] * ColBase;
        }
    }
}

// 重点内容，求 (x1, y1) 到 (x2, y2) 的哈希（前缀和）
inline ull calc(ull mat[][maxn], int _x1, int _y1, int _x2, int _y2) {
    ull res = mat[_x2][_y2];
    res -= mat[_x1 - 1][_y2] * col[_x2 - _x1 + 1]; // 乘上相应基数以对齐矩阵
    res -= mat[_x2][_y1 - 1] * row[_y2 - _y1 + 1];
    res += mat[_x1 - 1][_y1 - 1] * col[_x2 - _x1 + 1] * row[_y2 - _y1 + 1]; // 容斥原理
    return res;
}

inline bool check() {
    ull sub = calc(submat, 1, 1, a, b); // 查询矩阵的哈希
    for (int i = a; i <= n; i++) {
        for (int j = b; j <= m; j++) {
            if (calc(matrix, i - a + 1, j - b + 1, i, j) == sub) return true; // matrix 的子矩阵如果匹配到了就返回真
        }
    }
    return false; // 匹配不到
}

int main() {
    scanf("%d%d%d%d", &n, &m, &a, &b);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char ch;
            scanf(" %c", &ch);
            matrix[i][j] = ch - '0';
        }
    }
    hashInit(); // 哈希初始化
    int T;
    scanf("%d", &T);
    while (T--) {
        for (int i = 1; i <= a; i++) {
            for (int j = 1; j <= b; j++) {
                char ch;
                scanf(" %c", &ch);
                submat[i][j] = ch - '0';
            }
        }
        initSubmat();
        printf("%d\n", check());
    }
    return 0;
}

相关题目

P4398 JSOI2008 Blue Mary的战役地图 - 洛谷

这道题数据只有 \(50\)，可以用 DP，复杂度 \(O(n^4)\)，也可以用二维哈希。但是学校 OJ 给的数据范围是 \(500\)，所以 DP 过不了，朴素的二维哈希解本题的复杂度为 \(O(n^3)\)，也过不了。

我们发现如果两个方阵不存在长度为 \(k\) 相同的方阵，则不可能存在 \(\ge k\) 的方阵，如果存在，则有可能存在更大的，所以具有单调性，所以我们二分这个边长即可。复杂度 \(O(n^2 \log n)\)。

代码

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const ull RowBase = 37, ColBase = 13;
const int maxn = 505;
int n;
ull row[maxn], col[maxn];
ull alpha[maxn][maxn], beta[maxn][maxn];

ull calc(ull mat[][maxn], int x, int y, int len) {
    return mat[x][y] - mat[x - len][y] * col[len] - mat[x][y - len] * row[len]
        + mat[x - len][y - len] * row[len] * col[len];
}

void getHash(ull mat[][maxn]) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            mat[i][j] = mat[i][j - 1] * RowBase + mat[i][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            mat[i][j] = mat[i - 1][j] * ColBase + mat[i][j];
        }
    }
}

bool check(int len) {
    set<ull> exist;
    for (int i = len; i <= n; ++i) {
        for (int j = len; j <= n; ++j) {
            exist.insert(calc(alpha, i, j, len));
        }
    }
    for (int i = len; i <= n; ++i) {
        for (int j = len; j <= n; ++j) {
            if (exist.count(calc(beta, i, j, len))) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%lld", &alpha[i][j]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%lld", &beta[i][j]);
        }
    }
    row[0] = col[0] = 1;
    for (int i = 1; i <= n; ++i) {
        row[i] = row[i - 1] * RowBase;
    }
    for (int i = 1; i <= n; ++i) {
        col[i] = col[i - 1] * ColBase;
    }
    getHash(alpha);
    getHash(beta);
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    if (check(l)) printf("%d\n", l);
    else printf("%d\n", r);
    return 0;
}