Advertisement
playerr17

Untitled

Jan 6th, 2023
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.75 KB | None | 0 0
  1. char S[501][501];
  2. int H[501][501];
  3. int Px[501];
  4. int Py[501];
  5. int H1[501][501];
  6. int P1x[501];
  7. int P1y[501];
  8.  
  9. int get_hash(int x1, int y1, int x2, int y2) {
  10.     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;
  11. }
  12. int get_hash1(int x1, int y1, int x2, int y2) {
  13.     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;
  14. }
  15.  
  16. bool check(int k, int n, int m, int& x1, int& y1, int& x2, int& y2) {
  17.     unordered_map<ll, pair<int, int>> used;
  18.     forn(i, 1, n - k + 2) {
  19.         forn(j, 1, m - k + 2) {
  20.             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);
  21.             if (used.contains(h)) {
  22.                 x1 = used[h].f;
  23.                 y1 = used[h].s;
  24.                 x2 = i;
  25.                 y2 = j;
  26.                 return true;
  27.             }
  28.             used[h] = {i, j};
  29.         }
  30.     }
  31.     return false;
  32. }
  33.  
  34. void solve(){
  35.     int n, m;
  36.     cin >> n >> m;
  37.     forn1(i, 1, n) {
  38.         forn1(j, 1, m) {
  39.             cin >> S[i][j];
  40.         }
  41.     }
  42.     H[0][0] = 0;
  43.     forn1(i, 1, n) {
  44.         H[i][0] = 0;
  45.     }
  46.     forn1(i, 1, m) {
  47.         H[0][i] = 0;
  48.     }
  49.     forn1(i, 0, n) {
  50.         Px[i] = (i == 0 ? 1 : Px[i - 1] * 1ll * 57 % MOD);
  51.     }
  52.     forn1(i, 0, m) {
  53.         Py[i] = (i == 0 ? 1 : Py[i - 1] * 1ll * 41 % MOD);
  54.     }
  55.     forn1(i, 1, n) {
  56.         forn1(j, 1, m) {
  57.             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;
  58.         }
  59.     }
  60.     H1[0][0] = 0;
  61.     forn1(i, 1, n) {
  62.         H1[i][0] = 0;
  63.     }
  64.     forn1(i, 1, m) {
  65.         H1[0][i] = 0;
  66.     }
  67.     forn1(i, 0, n) {
  68.         P1x[i] = (i == 0 ? 1 : P1x[i - 1] * 1ll * 37 % MOD1);
  69.     }
  70.     forn1(i, 0, m) {
  71.         P1y[i] = (i == 0 ? 1 : P1y[i - 1] * 1ll * 43 % MOD1);
  72.     }
  73.     forn1(i, 1, n) {
  74.         forn1(j, 1, m) {
  75.             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;
  76.         }
  77.     }
  78.     int mi = 0, ma = min(n, m) + 1;
  79.     int x1;
  80.     int y1;
  81.     int x2;
  82.     int y2;
  83.     while(mi + 1 < ma) {
  84.         int sr = (mi + ma) / 2;
  85.         if (check(sr, n, m, x1, y1, x2, y2)) {
  86.             mi = sr;
  87.         } else {
  88.             ma = sr;
  89.         }
  90.     }
  91.     cout << mi << endl;
  92.     if (mi != 0) {
  93.         cout << x1 << ' ' << y1 << endl << x2 << ' ' << y2 << endl;
  94.     }
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement