Advertisement
Guest User

Untitled

a guest
Sep 4th, 2015
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. /* (c) Vladimir Yakovlev */
  2. #include <cstdio>
  3. #include <algorithm>
  4. using namespace std;
  5. typedef unsigned int uint;
  6. #define Max(x,y) ((x)<(y)?(y):(x))
  7. #define Min(x,y) ((x)<(y)?(x):(y))
  8. const int MAX = 512;
  9. const uint P = 1021;
  10. const uint Q = 4999;
  11. const uint MAXH = 1048575U;
  12.  
  13. int n, m;
  14. char s[MAX][MAX];
  15. uint hash[MAX][MAX];
  16. uint hashTemp[MAX];
  17. short hashX[MAXH];
  18. short hashY[MAXH];
  19. int x1, y1, x2, y2;
  20.  
  21. void CountHash(int k)
  22. {
  23.     int i, j;
  24.  
  25.     uint pk = 1;
  26.     uint qk = 1;
  27.     for (i=0; i<k; i++)
  28.     {
  29.         pk = pk*P;
  30.         qk = qk*Q;
  31.     }
  32.  
  33.     for (i=0; i<n; i++)
  34.     {
  35.         int c = 0;
  36.         for (j=0; j<m; j++)
  37.         {
  38.             c = c*P + s[i][j];
  39.             if (j-k >= 0)
  40.                 c -= s[i][j-k]*pk;
  41.             if (j-k+1 >= 0)
  42.                 hash[i][j-k+1] = c;
  43.         }
  44.     }
  45.  
  46.     for (j=0; j+k<=m; j++)
  47.     {
  48.         int c = 0;
  49.         for (i=0; i<n; i++)
  50.         {
  51.             c = c*Q + hash[i][j];
  52.             if (i-k >= 0)
  53.                 c -= hash[i-k][j]*qk;
  54.             if (i-k+1 >= 0)
  55.                 hashTemp[i-k+1] = c;
  56.         }
  57.         for (i=0; i<=n-k; i++)
  58.             hash[i][j] = hashTemp[i];
  59.     }
  60. }
  61.  
  62. bool Check(int i1, int j1, int i2, int j2, int k)
  63. {
  64.     if (hash[i1][j1] != hash[i2][j2])
  65.         return false;
  66.     for (int i=0; i<k; i++)
  67.         for (int j=0; j<k; j++)
  68.             if (s[i1+i][j1+j] != s[i2+i][j2+j])
  69.                 return false;
  70.     x1 = i1;
  71.     y1 = j1;
  72.     x2 = i2;
  73.     y2 = j2;
  74.     return true;
  75. }
  76.  
  77. bool Find(int k)
  78. {
  79.     CountHash(k);
  80.  
  81.     memset(hashX, -1, sizeof(hashX));
  82.     for (int i=0; i<=n-k; i++)
  83.         for (int j=0; j<=m-k; j++)
  84.         {
  85.             uint u;
  86.             for (u = hash[i][j]%MAXH; hashX[u] != -1; u = (u+1)%MAXH)
  87.                 if (Check(hashX[u], hashY[u], i, j, k))
  88.                     return true;
  89.             hashX[u] = i;
  90.             hashY[u] = j;
  91.         }
  92.     return false;
  93. }
  94.  
  95. int main()
  96. {
  97. #ifndef ONLINE_JUDGE
  98.     freopen("input.txt", "rt", stdin);
  99.     freopen("output.txt", "wt", stdout);
  100. #endif
  101.  
  102.     scanf("%d%d", &n, &m);
  103.     for (int i=0; i<n; i++)
  104.         scanf("%s", s[i]);
  105.  
  106.     int l = 0;
  107.     int r = Min(n, m);
  108.     while (l < r)
  109.     {
  110.         int c = (l+r+1) / 2;
  111.         if (Find(c))
  112.             l = c;
  113.         else
  114.             r = c-1;
  115.     }
  116.  
  117.     if (l == 0)
  118.     {
  119.         printf("0\n");
  120.     }
  121.     else
  122.     {
  123.         Find(l);
  124.         printf("%d\n%d %d\n%d %d\n", l, x1+1, y1+1, x2+1, y2+1);
  125.     }
  126.  
  127.     return 0;
  128. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement