牛客练习赛1 A - 矩阵

时间:2023-03-09 01:18:12
牛客练习赛1 A - 矩阵

链接:https://www.nowcoder.com/acm/contest/2/A
来源:牛客网

题目描述

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

输入描述:

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

输出描述:

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

输入例子:
5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl
输出例子:
3

-->

示例1

输入

5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl

输出

3

备注:

对于30%的数据,n,m≤100;
对于100%的数据,n,m≤500;

题解

二分,字符串$hash$。

可以二分答案,然后验证,验证的时候$O(n^2)$效率可以得到每一个正方形的$hash$值,判断一下即可,注意$hash$冲突,用了两次$hash$才过。

#include<bits/stdc++.h>
using namespace std; long long base[2];
long long mod[2];
const int maxn = 500 + 10;
int n, m;
char s[maxn][maxn];
long long b[2][maxn * maxn];
long long sum[2][maxn][maxn];
long long h[2][maxn][maxn];
pair<long long, long long> pi[maxn * maxn]; void init() {
base[0] = 131LL;
base[1] = 313LL;
mod[0] = 1e9 + 7;
mod[1] = 1e9 + 7;
} int check(int x) {
for(int t = 0; t < 2; t ++) {
for(int i = 0; i < n; i ++) {
long long C = 0;
for(int j = 0; j < x; j ++) {
C = C * base[t] % mod[t];
C = (C + s[i][j]) % mod[t];
}
sum[t][i][0] = C;
for(int j = 1; j + x - 1 < m; j ++) {
long long A = sum[t][i][j - 1];
long long B = s[i][j - 1] * b[t][x - 1] % mod[t];
A = (A - B + mod[t]) % mod[t];
A = A * base[t] % mod[t];
A = (A + s[i][j + x - 1]) % mod[t];
sum[t][i][j] = A;
}
}
for(int j = 0; j < m; j ++) {
long long C = 0;
for(int i = 0; i < x; i ++) {
C = C * b[t][x] % mod[t];
C = (C + sum[t][i][j]) % mod[t];
}
h[t][0][j] = C;
}
for(int i = 1; i + x - 1 < n; i ++) {
for(int j = 0; j + x - 1 < m; j ++) {
long long A = h[t][i - 1][j];
long long B = sum[t][i - 1][j] * b[t][x * (x - 1)] % mod[t];
A = (A - B + mod[t]) % mod[t];
A = A * b[t][x] % mod[t];
A = (A + sum[t][i + x - 1][j]) % mod[t];
h[t][i][j] = A;
}
}
} int sz = 0;
for(int i = 0; i + x - 1 < n; i ++) {
for(int j = 0; j + x - 1 < m; j ++) {
pi[sz].first = h[0][i][j];
pi[sz].second = h[1][i][j];
sz ++;
}
}
sort(pi, pi + sz);
for(int i = 1; i < sz; i ++) {
if(pi[i] == pi[i - 1]) return 1;
} return 0;
} int main() {
init();
b[0][0] = 1LL;
b[1][0] = 1LL;
for(int i = 1; i <= 250000; i ++) {
b[0][i] = b[0][i - 1] * base[0] % mod[0];
b[1][i] = b[1][i - 1] * base[1] % mod[1];
}
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++) {
scanf("%s", s[i]);
}
int L = 1, R = min(n, m), ans = 0;
while(L <= R) {
int mid = (L + R) / 2;
if(check(mid)) L = mid + 1, ans = mid;
else R = mid - 1;
}
printf("%d\n", ans);
return 0;
} /* 5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl */