本文共 1577 字，大约阅读时间需要 5 分钟。
不懂hash的话：
思路：对于一个大矩阵的每一个子矩阵都对应着一个hash值k， 当k出现2次以上时就满足要求
只是对长度进行二分就可以了。
收获：学会了hash算法
#include #include using namespace std;#define ll long long#define ull unsigned long longconst int maxn = 510;const ull base1 = 131;const ull base2 = 233;int n, m;char mp[maxn][maxn];ull has[maxn][maxn];ull p1[maxn], p2[maxn];map 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 (cin >> n >> m){ for (int i = 1; i <= n; ++i) cin >> (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; } } cout << ans << endl; }}
转载于:https://www.cnblogs.com/ALINGMAOMAO/p/10345873.html