矩阵
时间限制：1秒 空间限制：131072K
题目描述
给出一个n * m的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出最大正方形的边长。
输入描述:
第一行两个整数n, m代表矩阵的长和宽；
接下来n行，每行m个字符（小写字母），表示矩阵；
输出描述:
输出一个整数表示满足条件的最大正方形的边长。
示例1
输入
5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl
输出
3
备注:
对于30%的数据，n,m≤100；
对于100%的数据，n,m≤500；
题目链接：https://www.nowcoder.com/acm/contest/submit/f8363c912a4c48a28b80f47e7102b6b8?ACMContestId=2&tagId=4
思路：二分答案mid，然后检验是否存在两个相同的mid*mid的正方形
检验方法：
首先对于每个位置，求出它开始长度为mid的横行的hash值
然后对于hash值再求一次竖列的hash值
将第二次求出的hash值排序，如果存在两个相同的hash值则可行
下面给出AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')
f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
inline void write(ll x)
{
if(x<)
{
putchar('-');
x=-x;
}
if(x>)
write(x/);
putchar(x%+'');
}
char dp[][];
ll n,m;
ll p1[],p2[];
ll p[][];
ll h[];
inline bool checked(ll x)
{
//
for(ll i=;i<=n;i++)
{
ll ans=;
for(ll j=;j<x;j++)
{
ans=ans*(ll)('a')+dp[i][j];
p[i][j]=;
}
for(ll j=x;j<=m;j++)
{
ans=ans*(ll)('a')-p1[x]*dp[i][j-x]+dp[i][j];
p[i][j]=ans;
}
}
//
ll GG=;
for(ll i=x;i<=m;i++)
{
ll PP=;
for(ll j=;j<x;j++)
{
PP=PP*(ll)('a'+(ll)(('A'+)/+))+p[j][i];
}
for(ll j=x;j<=n;j++)
{
PP=PP*(ll)('a'+(ll)(('A'+)/+))-p2[x]*p[j-x][i]+p[j][i];
h[GG]=PP;
GG++;
}
}
sort(h,h+GG);
for(ll i=;i<GG;i++)
{
if(h[i-]==h[i])
return true;
}
return false;
}
int main()
{
n=read();
m=read();
memset(p,,sizeof(p));
for(ll i=;i<=n;i++)
{
scanf("%s",dp[i]+);
for(ll j=;j<=m;j++)
{
dp[i][j]=dp[i][j]-('a'-);
}
}
ll l=;
ll r=min(n,m);
memset(p1,,sizeof(p1));
memset(p2,,sizeof(p2));
p1[]=;
p2[]=;
for(ll i=;i<=r;i++)
{
p1[i]=p1[i-]*(ll)('a');
p2[i]=p2[i-]*(ll)('a'+(ll)(('A'+)/+));
}
ll mid;
ll k;
while(l<=r)
{
mid=(l+r)/;
if(checked(mid))
{
l=(k=mid)+;
}
else
r=mid-;
}
write(k);
return ;
}