二维hash

题目描述

给出一个n * m的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出最大正方形的边长。

输入描述:

第一行两个整数n, m代表矩阵的长和宽；
接下来n行，每行m个字符（小写字母），表示矩阵；

输出描述:

输出一个整数表示满足条件的最大正方形的边长。




https://www.nowcoder.com/acm/contest/submit/f8363c912a4c48a28b80f47e7102b6b8?ACMContestId=2&tagId=4


做了一题二维hash的题。
我的这个方法应该不是正宗的二维hash。
我的做法是，先对每一行进行一维hash
然后对于每一个正方形，就有k（正方形边长）个hash值，然后再对这个值hash
然后要手写一个类似map的东西，不然超时。

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef unsigned long long int LL;
int n, m;
const int maxn = 1e3 + 20, seed = 131;
char str[maxn][maxn];
LL po[maxn], str_hash[maxn][maxn];
int ask(int row, int be, int len) {
    return str_hash[row][be + len - 1] - po[len] * str_hash[row][be - 1];
}
LL thash[maxn];
const int MOD = 10007;
struct StringHash {
    int first[MOD + 2], num;
    LL EdgeNum[1000000 + 2];
    int tonext[1000000 + 2];
    void init() {
        num = 0;
        memset(first, -1, sizeof first);
    }
    void toinsert(LL val) {
        EdgeNum[num] = val;
        int u = val % MOD;
        tonext[num] = first[u];
        first[u] = num++;
    }
    bool has(LL val) {
        int u = val % MOD;
        for (int i = first[u]; ~i; i = tonext[i]) {
            if (EdgeNum[i] == val) return true;
        }
        return false;
    }
} my;
bool check(int val) {
    my.init();
    for (int i = 1; i + val - 1 <= m; ++i) {
        for (int j = 1; j <= n; ++j) {  //从上到下做
            thash[j] = thash[j - 1] * seed + ask(j, i, val);
        }
        for (int j = val; j <= n; ++j) { //才能O(1)得到值
            LL th = thash[j] - po[val] * thash[j - val];
            if (my.has(th)) return true;
            my.toinsert(th);
        }
    }
    return false;
}
void work() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%s", str[i] + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            str_hash[i][j] = str_hash[i][j - 1] * seed + str[i][j];
        }
    }
    int be = 1, en = min(n, m);
    while (be <= en) {
        int mid = (be + en) >> 1;
        if (check(mid)) be = mid + 1;
        else en = mid - 1;
    }
    if (en == 0) {
        printf("%d
", en);
        return;
    }
    printf("%d
", en);
//    printf("%d %d
", ans1.first, ans1.second);
//    printf("%d %d
", ans1.first + anslen - 1, ans1.second + anslen - 1);
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    po[0] = 1;
    for (int i = 1; i <= maxn - 20; ++i) po[i] = po[i - 1] * seed;
    work();
    return 0;
}