Description：

给两个方阵，求这两个方阵的最大子方阵的边长。

$1\le n \le 50$

Solution：

矩阵 $hash$ ，大概就是把矩阵的每一行做 $hash$ ，在把每一行的 $hash$ 值作为元素 $hash$ ，这样预处理 $O(n^2)$ ，单次求子矩阵 $hash$ 是 $O(n)$ 的，于是二分一个长度 $O(n^2)$ 把所有子矩阵的值丢到 $map$ 里，再 $O(n^2)$ 算第二个矩阵的 $hash$ 值在 $map$ 里查询即可。

时间复杂度 $O(n^3\log^2 n)$

Solution：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n;

#define MAXN 51

int a[MAXN][MAXN],b[MAXN][MAXN];

typedef long long ll;

ll ha[MAXN][MAXN],hb[MAXN][MAXN];

#define BASE1 998255353ll

ll power[MAXN];

#define BASE2 19260817ll

#define MOD 1000000007ll

#define rint register int

inline int read()

{

    rint res = 0,f = 1;

    char c = getchar();

    while(!isdigit(c))

    {

        if(c == '-')f = -1;

        c = getchar();

    }

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res * f;

}

map<ll,bool> tag;

inline ll calc1(int x,int y,int l)

{

    ll val = 0;

    for(rint i = x;i <= x + l - 1;++i)

        val = (val * BASE2 + ha[i][y + l - 1] - ha[i][y - 1] * power[l] % MOD + MOD) % MOD;

    return val;

}

inline ll calc2(int x,int y,int l)

{

    ll val = 0;

    for(rint i = x;i <= x + l - 1;++i)

        val = (val * BASE2 + hb[i][y + l - 1] - hb[i][y - 1] * power[l] % MOD + MOD) % MOD;

    return val;

}

inline bool check(int l)

{

    tag.clear();

    for(rint i = 1;i <= n - l + 1;++i)

        for(rint j = 1;j <= n - l + 1;++j)

            tag[calc1(i,j,l)] = true;

    for(rint i = 1;i <= n - l + 1;++i)

        for(rint j = 1;j <= n - l + 1;++j)

            if(tag.find(calc2(i,j,l)) != tag.end())return true;

    return false;

}

int main()

{

    scanf("%d",&n);

    power[0] = 1;for(rint i = 1;i <= 50;++i)power[i] = power[i - 1] * BASE1 % MOD;

    for(rint i = 1;i <= n;++i)

        for(rint j = 1;j <= n;++j)

            a[i][j] = read();

    for(rint i = 1;i <= n;++i)

        for(rint j = 1;j <= n;++j)

            ha[i][j] = (ha[i][j - 1] * BASE1 % MOD + a[i][j]) % MOD;

    for(rint i = 1;i <= n;++i)

        for(rint j = 1;j <= n;++j)

            b[i][j] = read();

    for(rint i = 1;i <= n;++i)

        for(rint j = 1;j <= n;++j)

            hb[i][j] = (hb[i][j - 1] * BASE1 % MOD + b[i][j]) % MOD;

    rint l = 0,r = n,mid;

    while(l < r)

    {

        mid = ((l + r + 1) >> 1);

        if(check(mid))l = mid;

        else r = mid - 1;

    }

    printf("%d\n",l);

    return 0;

}