2022.9.26

不会写就算了，结果题解只有一份代码，所以在观摩了别人的代码后，决定给各位撑把伞，第一次写题解见谅。

一.如何快速比较两个正方形矩阵是不是相同。

把字符转化数字求解，定义base1，base2为基数3，7； has[i][j] = has[i][j-1]*base1 + mp[i][j] - 'a';

has[i][j] = has[i-1][j]*base2 + has[i][j];

这个时候has[i][j]转化过来的数字就是0.0到i.j这个矩阵的特征值k。

has[i][j]通过某种运算与has[i-x][j-x],就可以得到（i-x，j-x）到（i，j)这个小矩阵的特征值k,如果k1=k2,则这两个小矩阵相同。

**补充（这里通过map存储了k的出现次数当k1=k2则k对应的键值对>=2说明找到了答案，如果不熟悉map可以去了解一下。）

k = has[i][j] - has[i-x][j]*p2[x] - has[i][j-x]*p1[x] + has[i-x][j-x]*p1[x]*p2[x];具体见代码理解，与base1,base2的乘法相关。

二.二分查找 正方形的边长最大才500，（l=0，r=600）不断求mid=（r+l）/2，如果找到了mid成立就找更大的mid，没找到就继续找最大的mid。

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

const ll base1=3,base2=7;

ll p1[505],p2[505];

ll has[505][505];

char mp[505][505];

map<ll,int>mmp;

int n,m;

void init(){

p1[0]=1;
p2[0]=1;
for(int i=1;i<=505;i++)
{
    p1[i]=p1[i-1]*base1;
    p2[i]=p2[i-1]*base2;
}
//为后面运算k做准备。

}

void hash1(){

for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        has[i][j]=has[i][j-1]*base1+mp[i][j]-'a';
    }
}
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        has[i][j]=has[i-1][j]*base2+has[i][j];
    }
}
//把字符的矩阵转化为数字。

}

bool check(int mid){

mmp.clear();
for(int i=mid;i<=n;i++)
{
    for(int j=mid;j<=m;j++)
    {
        //求小矩阵的特征值。
        ll k=(has[i][j] - has[i-mid][j]*p2[mid] - has[i][j-mid]*p1[mid] + has[i-mid][j-mid]*p1[mid]*p2[mid]);
        mmp[k]++;
        //当特征值k出现两次说明有两个矩阵相同。
        if(mmp[k] >= 2)
            return true;
    }
}
return false;

} int main(){

int i,j,k,x,y,ans=0;
cin>>n>>m;
for(i=1;i<=n;i++)
{
    for(j=1;j<=m;j++)
    {
        cin>>mp[i][j];
    }
}
init();
hash1();
/*for(i=1;i<=n;i++)
{
    for(j=1;j<=m;j++)
    {
        cout<<has[i][j]<<"  ";
    }
    cout<<endl;
}*/
//如果出现错误可以检查has，p1,p2，mid的变化。
int l=0,r=600,mid=0,t=0;
while(l<=r)
{
    mid=(l+r)/2;
    if(check(mid))
    {
        //二分查找。
        l = mid+1;
        ans = mid;
    }
    else
        r=mid-1;

}
cout<<ans<<endl;
}