URAL 1486（二维字符串HASH）

╰+哭是因爲堅強的太久メ 2021-10-15 08:29 211阅读 0赞

## 题意：给定一个n\*m的字符矩阵，问你是否存在两个不重合(可以有交集)的正方形矩阵完全一致， 存在输出正方形的最大边长和两个正方形的左上角坐标，不存在则输出0。 ##

## 分析：二维字符串Hash板子题，二分正方形的长度，然后Hash判断即可。注意进制P和模数M的选择，按照《算法竞赛进阶指南》上的来说，P一般可以选择131或者13331，推荐论文：《Hash在信息学竞赛中的一类应用》。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ull unsigned long long
    #define k1 131
    #define k2 13331
    const int N=5e2+5;
    int n,m,sx,sy,ex,ey,ans;
    ull hs[N][N],bin1[N],bin2[N];
    char s[N];
    
    int check(int l) {
        map<ull,int>mp;
        pair<int,int> p[N*N];
        int k=0;
        for(int i=l;i<=n;++i) {
            for(int j=l;j<=m;++j) {
                ull tmp = hs[i][j]-hs[i-l][j]*bin2[l]-hs[i][j-l]*bin1[l]+hs[i-l][j-l]*bin2[l]*bin1[l];///容斥
                if(mp[tmp]) {
                    sx=p[mp[tmp]].first,sy=p[mp[tmp]].second;
                    ex=i-l+1,ey=j-l+1;
                    return 1;
                }
                k++;
                mp[tmp]=k;
                p[k]={i-l+1,j-l+1};
            }
        }
        return 0;
    }
    
    int main() {
        scanf("%d%d",&n,&m);
        bin1[0]=bin2[0]=1;
        for(int i=1;i<=n;++i) {
            scanf("%s",s+1);
            for(int j=1;j<=m;++j)
                hs[i][j]=hs[i][j-1]*k1+s[j];
        }
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                hs[i][j]+=hs[i-1][j]*k2;
        for(int i=1;i<=n;++i)
            bin2[i]=bin2[i-1]*k2;
        for(int i=1;i<=m;++i)
            bin1[i]=bin1[i-1]*k1;
        int l=0,r=min(n,m);
        while(l<=r) {
            int mid=(l+r)/2;
            if(check(mid)) l=mid+1,ans=mid;
            else r=mid-1;
        }
        if(!ans) {
            printf("0\n");
            return 0;
        }
        printf("%d\n",ans);
        printf("%d %d\n%d %d\n",sx,sy,ex,ey);
        return 0;
    }