题目
https://ac.nowcoder.com/acm/contest/2?&headNav=www#question
解析 我们对矩阵进行二维hash,所以每个子矩阵都有一个额hash值,二分答案然后O(n^2) check 枚举矩阵终点,记录每个hash值与有两个一样的就true
AC代码
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; const int maxn=2e6+10; const ull base1=131,base2=233; //base,基数 int n, m; char mp[510][510]; ull has[510][510]; ull p1[510], p2[510]; map<ull, int> mmp; void init() { p1[0] = p2[0] = 1; for(int i = 1; i <= 505; i ++) { p1[i] = p1[i-1]*base1; p2[i] = p2[i-1]*base2; } } void Hash() { has[0][0] = 0; has[0][1] = 0; has[1][0] = 0; 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 x) { mmp.clear(); for(int i = x; i <= n; i ++) { for(int j = x; j <= m; j ++) { ull 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]; mmp[k] ++; if(mmp[k] >= 2) return true; } } return false; } int main() { init(); while(~scanf("%d%d", &n, &m)) { for(int i = 1; i <= n; i ++) { scanf("%s", mp[i]+1); } Hash(); int l = 0, r = 600, ans = 0; while(l <= r) { int mid = (l+r)/2; if(check(mid)) { l = mid+1; ans = mid; } else { r = mid-1; } } printf("%d\n", ans); } return 0; }