本文共 1991 字，大约阅读时间需要 6 分钟。

题意

给你两个矩阵，问你最大的相同正方形的边长是多少

题解

二维hash

#include
   
    #include
    
     #include
     
      typedef long long LL;const LL MOD=10037;//行const LL MOD1=100003;//列 const LL MOD2=1000000007; //总共 const LL N=55;LL n;LL a[N][N];LL f[N][N];//hash的矩阵LL f1[N][N];LL G[N],G1[N];LL Get (LL x,LL y,LL z)//以x,y为左上角 {    LL c=x+z-1,d=y+z-1;    LL ans=(f[c][d]-f[x-1][d]*G1[z]%MOD2)%MOD2;    ans=(ans-f[c][y-1]*G[z]%MOD2)%MOD2;    ans=(ans+f[x-1][y-1]*G[z]%MOD2*G1[z]%MOD2)%MOD2;    ans=(ans+MOD2)%MOD2;    return ans;}LL Get1 (LL x,LL y,LL z)//以x,y为左上角 {    LL c=x+z-1,d=y+z-1;    LL ans=(f1[c][d]-f1[x-1][d]*G1[z]%MOD2)%MOD2;    ans=(ans-f1[c][y-1]*G[z]%MOD2)%MOD2;    ans=(ans+f1[x-1][y-1]*G[z]%MOD2*G1[z]%MOD2)%MOD2;    ans=(ans+MOD2)%MOD2;    return ans;}void Ins (){    scanf("%lld",&n);    for (LL u=1;u<=n;u++)        for (LL i=1;i<=n;i++)            scanf("%lld",&a[u][i]);    for (LL u=1;u<=n;u++)        for (LL i=1;i<=n;i++)            f[u][i]=(f[u][i-1]*MOD+a[u][i])%MOD2;    for (LL u=1;u<=n;u++)        for (LL i=1;i<=n;i++)            f[i][u]=(f[i-1][u]*MOD1+f[i][u])%MOD2;    for (LL u=1;u<=n;u++)        for (LL i=1;i<=n;i++)            scanf("%lld",&a[u][i]);    for (LL u=1;u<=n;u++)        for (LL i=1;i<=n;i++)            f1[u][i]=(f1[u][i-1]*MOD+a[u][i])%MOD2;    for (LL u=1;u<=n;u++)        for (LL i=1;i<=n;i++)            f1[i][u]=(f1[i-1][u]*MOD1+f1[i][u])%MOD2;}bool check (LL u){    for (LL i=1;i<=n-u+1;i++)        for (LL j=1;j<=n-u+1;j++)            for (LL k=1;k<=n-u+1;k++)                for (LL l=1;l<=n-u+1;l++)                    if (Get(i,j,u)==Get1(k,l,u))                        return true;    return false;}int main(){    Ins();    G[0]=1;for (LL u=1;u<=n;u++) G[u]=(G[u-1]*MOD)%MOD2;    G1[0]=1;for (LL u=1;u<=n;u++) G1[u]=(G1[u-1]*MOD1)%MOD2;    LL l=1,r=n;    LL ans=0;    while (l<=r)    {        LL mid=(l+r)>>1;        if (check(mid)) {ans=mid;l=mid+1;}        else r=mid-1;    }    printf("%lld\n",ans);    return 0;}