题目描述
给出一个n * m的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出最大正方形的边长。
输入描述:
第一行两个整数n, m代表矩阵的长和宽； 接下来n行，每行m个字符（小写字母），表示矩阵；
输出描述:
输出一个整数表示满足条件的最大正方形的边长。
输入
5 10 ljkfghdfas isdfjksiye pgljkijlgp eyisdafdsi lnpglkfkjl
输出
3
备注:
对于30%的数据，n,m≤100； 对于100%的数据，n,m≤500；
题目分析
由数据规模可推出时间复杂度应不高于。
如果暴力遍历，则时间复杂度为及以上。
考虑使用二维字符串哈希，便于快速比较两个不同的字符正方形是否相同；
同时，考虑遍历正方形边长时，使用二分查找方法。
题目代码
关于，二分查找也可以看下这篇文章，里面有些资源可以帮助理解。
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long; //使用ull可自动取模2^64
const int N = 5e2 + 10;
const int base1 = 131, base2 = 233; //用于哈希
ull p1[N], p2[N];
map<ull, int> mp; //统计哈希值为X的正方形个数
char s[N][N]; //原字符数组
ull h[N][N]; //哈希数组
int n, m;
//由于要求前缀和，所以下标均从1开始
bool val(int x){ //求解
mp.clear(); //记得清除映射
for(int i = x; i <= n; ++i){
for(int j = x; j <= m; ++j){
ull k = h[i][j] - h[i-x][j]*p2[x] - h[i][j-x]*p1[x] + h[i-x][j-x]*p2[x]*p1[x];
++mp[k];
if(mp[k] > 1) return true;
}
}
return false; //不满足条件
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; ++i) scanf("%s", (s[i]+1));
//1. 预处理哈希的幂次方, 用于后续字符串对齐
p1[0] = p2[0] = 1; //！
for(int i = 1; i < N; ++i){
p1[i] = p1[i-1] * base1;
p2[i] = p2[i-1] * base2;
}
//2. 计算二维字符串前缀和
//2.1 计算一维 行 前缀和
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
h[i][j] = h[i][j - 1] * base1 + (s[i][j]-'a');
//2.2 计算以(i,j)为右下角的二维 矩阵 前缀和
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
h[i][j] = h[i-1][j] * base2 + h[i][j];
//3. 二分法求解满足条件的正方形最大的边长
// //此处二分法使用开区间方法 (l, r)为待查找区间
// int l = 0, r = min(n,m)+1;
// while(l < r-1){
// int mid = l + (r-l)/2;
// if(val(mid)) l = mid;
// else r = mid;
// } // 出来时， l == r-1
// //[0, l]满足条件, ..., [r, min(n,m)]不满足条件
// //l即为所求
// cout << l << endl;
// //此处二分法使用闭区间方法 [l,r]为待查找区间
// int l = 1, r = min(n, m);
// while(l <= r){
// int mid = l + (r-l)/2;
// if(val(mid)) l = mid+1;
// else r = mid-1;
// } //出来时，r == l-1
// //[0, l)满足条件，...，(r, min(n,m)]不满足条件
// //l-1即为所求
// cout << l-1 << endl;
//此处二分法使用左开右闭区间方法 [l, r)为待查找区间
int l = 1, r = min(n,m)+1;
while(l < r){
int mid = l + (r-l)/2;
if(val(mid)) l = mid+1;
else r = mid;
} //出来时，l == r
//[0, l)均满足条件，...，[r, min(n,m)]均不满足条件
//l-1即为所求
cout << l-1 << endl;
return 0;
}三种二分查找均已通过！🎉
