首先二分答案ans，然后只要进行判断答案ans是否可行即可。
验证方法：首先对每一个位置，求出它开始长度为ans的横行的hash值
然后求出每一个hash值的长度为ans的竖列的Hash值
查看是否有两个Hash值相同即可（比如我们可以基数排序。。。做什么大死！）
1 /************************************************************** 2 Problem: 1397 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:2084 ms 7 Memory:5052 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 13 using namespace std; 14 typedef long long ll; 15 16 const ll B1 = 103; 17 const ll B2 = 211; 18 const int N = 505; 19 20 int n, m; 21 char a[N][N]; 22 ll p1[N], p2[N]; 23 ll h[N][N], hash[N * N]; 24 25 bool check(int x) { 26 int i, j, t; 27 ll tmp; 28 for (i = 1; i <= n; ++i) { 29 for (tmp = 0, j = 1; j < x; ++j) 30 (tmp *= B1) += a[i][j], h[i][j] = 0; 31 for (j = x; j <= m; ++j) 32 h[i][j] = tmp = tmp * B1 - p1[x] * a[i][j - x] + a[i][j]; 33 } 34 for (t = 0, i = x; i <= m; ++i) { 35 for (tmp = 0, j = 1; j < x; ++j) 36 (tmp *= B2) += h[j][i]; 37 for (j = x; j <= n; ++j) 38 hash[t++] = tmp = tmp * B2 - p2[x] * h[j - x][i] + h[j][i]; 39 } 40 sort(hash, hash + t); 41 for (i = 1; i < t; ++i) 42 if (hash[i] == hash[i - 1]) return 1; 43 return 0; 44 } 45 46 int main() { 47 int i, j, l, r, mid; 48 scanf("%d%d ", &n, &m); 49 for (i = 1; i <= n; ++i) { 50 gets(a[i] + 1); 51 for (j = 1; j <= m; ++j) 52 a[i][j] -= 'a' - 1; 53 } 54 l = 1, r = min(n, m) + 1, p1[0] = p2[0] = 1; 55 for (i = 1; i <= r; ++i) 56 p1[i] = p1[i - 1] * B1, p2[i] = p2[i - 1] * B2; 57 while (l + 1 < r) { 58 mid = (l + r) >> 1; 59 if (check(mid)) l = mid; 60 else r = mid; 61 } 62 printf("%d ", l); 63 return 0; 64 }