Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- char S[501][501];
- int H[501][501];
- int Px[501];
- int Py[501];
- int H1[501][501];
- int P1x[501];
- int P1y[501];
- int get_hash(int x1, int y1, int x2, int y2) {
- return ((1ll * H[x2][y2] - 1ll * H[x1 - 1][y2] * Px[x2 - x1 + 1] - 1ll * H[x2][y1 - 1] * Py[y2 - y1 + 1] + 1ll * H[x1 - 1][y1 - 1] *(1ll* Py[y2 - y1 + 1] * Px[x2 - x1 + 1] % MOD)) % MOD + MOD) % MOD;
- }
- int get_hash1(int x1, int y1, int x2, int y2) {
- return ((1ll * H1[x2][y2] - 1ll * H1[x1 - 1][y2] * P1x[x2 - x1 + 1] - 1ll * H1[x2][y1 - 1] * P1y[y2 - y1 + 1] + 1ll * H1[x1 - 1][y1 - 1] *(1ll* P1y[y2 - y1 + 1] * P1x[x2 - x1 + 1] % MOD1)) % MOD1 + MOD1) % MOD1;
- }
- bool check(int k, int n, int m, int& x1, int& y1, int& x2, int& y2) {
- unordered_map<ll, pair<int, int>> used;
- forn(i, 1, n - k + 2) {
- forn(j, 1, m - k + 2) {
- ll h = get_hash1(i, j, i + k - 1, j + k - 1) * ll(1e9) + 1ll * get_hash(i, j, i + k - 1, j + k - 1);
- if (used.contains(h)) {
- x1 = used[h].f;
- y1 = used[h].s;
- x2 = i;
- y2 = j;
- return true;
- }
- used[h] = {i, j};
- }
- }
- return false;
- }
- void solve(){
- int n, m;
- cin >> n >> m;
- forn1(i, 1, n) {
- forn1(j, 1, m) {
- cin >> S[i][j];
- }
- }
- H[0][0] = 0;
- forn1(i, 1, n) {
- H[i][0] = 0;
- }
- forn1(i, 1, m) {
- H[0][i] = 0;
- }
- forn1(i, 0, n) {
- Px[i] = (i == 0 ? 1 : Px[i - 1] * 1ll * 57 % MOD);
- }
- forn1(i, 0, m) {
- Py[i] = (i == 0 ? 1 : Py[i - 1] * 1ll * 41 % MOD);
- }
- forn1(i, 1, n) {
- forn1(j, 1, m) {
- H[i][j] = ((H[i - 1][j] * 1ll * 57 + H[i][j - 1] * 1ll * 41 - H[i - 1][j - 1] * 1ll * 57 * 41 + 1ll * (S[i][j] - 'a' + 1)) % MOD + MOD) % MOD;
- }
- }
- H1[0][0] = 0;
- forn1(i, 1, n) {
- H1[i][0] = 0;
- }
- forn1(i, 1, m) {
- H1[0][i] = 0;
- }
- forn1(i, 0, n) {
- P1x[i] = (i == 0 ? 1 : P1x[i - 1] * 1ll * 37 % MOD1);
- }
- forn1(i, 0, m) {
- P1y[i] = (i == 0 ? 1 : P1y[i - 1] * 1ll * 43 % MOD1);
- }
- forn1(i, 1, n) {
- forn1(j, 1, m) {
- H1[i][j] = ((H1[i - 1][j] * 1ll * P1x[1] + H1[i][j - 1] * 1ll * P1y[1] - H1[i - 1][j - 1] * 1ll * P1x[1] * P1y[1] + 1ll * (S[i][j] - 'a' + 1)) % MOD1 + MOD1) % MOD1;
- }
- }
- int mi = 0, ma = min(n, m) + 1;
- int x1;
- int y1;
- int x2;
- int y2;
- while(mi + 1 < ma) {
- int sr = (mi + ma) / 2;
- if (check(sr, n, m, x1, y1, x2, y2)) {
- mi = sr;
- } else {
- ma = sr;
- }
- }
- cout << mi << endl;
- if (mi != 0) {
- cout << x1 << ' ' << y1 << endl << x2 << ' ' << y2 << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement