二维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 + , seed = ;

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 - ] - po[len] * str_hash[row][be - ];

}

LL thash[maxn];

const int MOD = ;

struct StringHash {

    int first[MOD + ], num;

    LL EdgeNum[ + ];

    int tonext[ + ];

    void init() {

        num = ;

        memset(first, -, 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 = ; i + val -  <= m; ++i) {

        for (int j = ; j <= n; ++j) {  //从上到下做

            thash[j] = thash[j - ] * 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 = ; i <= n; ++i) scanf("%s", str[i] + );

    for (int i = ; i <= n; ++i) {

        for (int j = ; j <= m; ++j) {

            str_hash[i][j] = str_hash[i][j - ] * seed + str[i][j];

        }

    }

    int be = , en = min(n, m);

    while (be <= en) {

        int mid = (be + en) >> ;

        if (check(mid)) be = mid + ;

        else en = mid - ;

    }

    if (en == ) {

        printf("%d\n", en);

        return;

    }

    printf("%d\n", en);

//    printf("%d %d\n", ans1.first, ans1.second);

//    printf("%d %d\n", ans1.first + anslen - 1, ans1.second + anslen - 1);

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    po[] = ;

    for (int i = ; i <= maxn - ; ++i) po[i] = po[i - ] * seed;

    work();

    return ;

}

巴特西

二维hash

题目描述

输入描述:

输出描述:

最新文章

热门文章