https://ac.nowcoder.com/acm/problem/13610
题意中文的，很简单
做法，二分加哈希，关于二维字符串怎么哈希，公式可以去看看这个
https://blog.csdn.net/KXL5180/article/details/90447007
还有需要注意的就是题目他卡了map 要用 unordered_map才能过
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const ull hs1=200379; const ull hs2=196613; const ll mod=1e9+7; const int N=1010; ull p1[N],p2[N]; ull hs[N][N]; int m,n; char s[N][N]; void init() { p1[0]=p2[0]=1; for(int i=1;i<N;i++) p1[i]=p1[i-1]*hs1; for(int i=1;i<N;i++) p2[i]=p2[i-1]*hs2; } int judge(int x) { ull cnt; unordered_map<ull,int>mp; for(int i=x;i<=n;i++) { for(int j=x;j<=m;j++) { cnt=hs[i][j]-hs[i-x][j]*p1[x]-hs[i][j-x]*p2[x]+hs[i-x][j-x]*p1[x]*p2[x]; mp[cnt]++; if(mp[cnt]==2) return 1; } } return 0; } int main() { init(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",s[i]+1); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { hs[i][j]=hs[i][j-1]*hs2+hs[i-1][j]*hs1-hs[i-1][j-1]*hs1*hs2+s[i][j]; } } int l=0,r=min(n,m),mid,ans; while(l<=r) { mid=(l+r)>>1; if(judge(mid)) { ans=mid; l=mid+1; } else r=mid-1; } printf("%d\n",ans); return 0; }
