Advertisement
Guest User

Untitled

a guest
Feb 1st, 2011
307
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.50 KB | None | 0 0
  1.     /*описание tl10-решения задачи №1486-timus:
  2.     1. делам преподсчет "префиксов" для квадратов из букв, чтобы потом можно было найти хэш от любого квадрта за О(1)
  3.     2. Бинарный алгоритмом проходимся по длине стороны квадрата, что нужно найти
  4.     3. Осуществляем перебор всех квадратов (со стороной длину которого мы находим в пункте 2)
  5.     4. при этом все сгенерированные хэши попадают в дерево поиска tree666 для того чтобы можно было проверять за O(log N * M) есть ли этот хэш.
  6.     5. если хэш нашли то просто выходим
  7.     6. если одинаковые хэши не найдены, то отчищаем дерево так как эти хэши уже не нужны
  8.     */
  9. #include <iostream>
  10. #include <vector>
  11. #include <string>
  12. #include <algorithm>
  13. #include <set>
  14. #include <map>
  15. using namespace std;
  16. #define ULL unsigned long long
  17. #define US unsigned short
  18. int p = 29;
  19. int q = 31;
  20. int ansx = 0,ansy = 0;
  21. int ansx2 = 0,ansy2 = 0;
  22. ULL p_powx[500] = {0};
  23. ULL p_powy[500] = {0};
  24. template<class T>
  25. struct node//дерево нужно для поиска одинаковых хэшей за О(log n * m)
  26. {
  27.     T value;//хэш
  28.     US l,r; //координаты квадрта
  29.     node *pleft,*pright;
  30.     node() : pleft(0),pright(0){};
  31. };
  32. template<class T>
  33. void addToTree (node<T> **pF,T x,US l,US r)
  34. {
  35.     if(!(*pF))
  36.     {
  37.         *pF = new node<T>();   
  38.         (*pF)->value = x;
  39.         (*pF)->l = l;
  40.         (*pF)->r = r;
  41.     }
  42.     else
  43.     {
  44.         if((*pF)->value > x)   
  45.             addToTree (&((*pF)->pleft),x,l,r);
  46.         else             
  47.             addToTree (&((*pF)->pright),x,l,r);
  48.     }
  49. }
  50. template<class T>
  51. bool findInsideTree (node<T>* p,T x) {//поиск одинаковых хэшей
  52.   if(!p)
  53.       return false;
  54.   if(p->value == x)
  55.   {//нашли одинаковые хэши
  56.       ansx = p->l;//запомнили координаты
  57.       ansy = p->r;
  58.       return true;
  59.   }
  60.   if(x < p->value)
  61.       return findInsideTree (p->pleft,x);
  62.   else
  63.       return findInsideTree (p->pright,x);
  64. }
  65.  
  66. template<class T>
  67. void deltree (node<T>* p) {//удаление дерева
  68.     if (!p->pleft && !p->pright)
  69.     {
  70.         p->value = 0;
  71.         delete p;
  72.     }
  73.     else if (!p->pleft && p->pright)
  74.     {
  75.         deltree (p->pright);
  76.         p->value = 0;
  77.         delete p;
  78.     }
  79.     else if (p->pleft && !p->pright)
  80.     {
  81.         deltree (p->pleft);
  82.         p->value = 0;
  83.         delete p;
  84.     }
  85.     else if(p->pleft && p->pright)
  86.     {
  87.         deltree (p->pleft);
  88.         deltree (p->pright);
  89.         delete p;
  90.     }
  91.     p = NULL;
  92. }
  93. node<ULL> *tree666;//обычно двоичное дерево где будут храиться хэши для быстрого поиска
  94. ULL pref[500][500] = {0};//префиксы квадратов
  95. int N,M;
  96. bool find_common_squar (int m)//поиск одинаковы квадратов или хэшей
  97. {
  98.     int indgl = 0;
  99.     int rlt = m - 1;
  100.     for (int i = 0; i < N - rlt; i++)
  101.     {
  102.         for (int j = 0; j < M - rlt; j++)
  103.         {//за 1 находим хэш квадрата заключенного между i,j  i + m,j + m
  104.             ULL hash = pref[rlt + i][rlt + j];
  105.             if (i && j)
  106.                 hash -= (pref[i - 1][rlt + j] + pref[rlt + i][j - 1] - pref[i - 1][j - 1]);
  107.             else if (i)
  108.                 hash -= pref[i - 1][rlt + j];
  109.             else if (j)
  110.                 hash -= pref[rlt + i][j - 1];
  111.             hash *= p_powx[N - rlt - i - 1] * p_powy[M - rlt - j - 1];
  112.             if (findInsideTree (tree666,hash))//поиск
  113.             {//нашли одинаковые хэши
  114.                 ansx2 = i;
  115.                 ansy2 = j;
  116.                 return true;
  117.             }
  118.             addToTree (&tree666,hash,i,j);//добавить хэш в дерево поиска
  119.         }
  120.     }
  121.     deltree (tree666);//отчистить дерево поиска так как эти хэши уже не нужны
  122.     tree666 = NULL;
  123.     return false;
  124. }
  125. int main()
  126. {
  127.  
  128.     //freopen("input.txt","r",stdin);
  129.     //freopen("output.txt","w",stdout);
  130.     int n,m;
  131.     scanf ("%d%d\n",&n,&m);
  132.     p_powx[0] = 1;
  133.     for (int i = 1; i < n; i++)
  134.         p_powx[i] = p_powx[i - 1] * p;//табличка по первому простому числу
  135.     N = n;
  136.     p_powy[0] = 1;
  137.     for (int i = 1; i < m; i++)
  138.         p_powy[i] = p_powy[i - 1] * q;//табличка по второу простому числу
  139.      M = m;
  140.     for (int i = 0; i < n; i++)
  141.     {
  142.         for (int j = 0; j < m; j++)
  143.         {
  144.             char ch;
  145.             scanf ("%c",&ch);
  146.             pref[i][j] = (ch - 'a' + 1) * p_powx[i] * p_powy[j]; //квадратные префиксы
  147.             if (i && j)
  148.             {
  149.                 pref[i][j] += (pref[i][j - 1] + pref[i - 1][j] - pref[i - 1][j - 1]);//убрать лишние квадрта, или выделить нужный квадрат
  150.             }
  151.             else if (i)
  152.             {//тоже
  153.                 pref[i][j] += pref[i - 1][j];
  154.             }
  155.             else if (j)
  156.             {//тоже
  157.                 pref[i][j] += pref[i][j - 1];
  158.             }
  159.         }
  160.         scanf ("\n");
  161.     }
  162.     int L = 1;
  163.     int R = min (n,m);
  164.     int ind = 1;
  165.     while (L < R)//бинарный поиск по длине стороны квадрата
  166.     {
  167.         int mid = (L + R) / 2;
  168.         if(find_common_squar (mid))
  169.         {
  170.             ind = mid;
  171.             L = mid + 1;
  172.         }
  173.         else
  174.             R = mid;
  175.     }
  176.     if(find_common_squar (L))
  177.     {
  178.         printf ("%d\n",L);
  179.         printf ("%d %d\n",ansx + 1,ansy + 1);
  180.         printf ("%d %d",ansx2 + 1,ansy2 + 1);
  181.     }
  182.     else if(ind != 1)
  183.     {
  184.         printf ("%d\n",ind);
  185.         printf ("%d %d\n",ansx + 1,ansy + 1);
  186.         printf ("%d %d",ansx2 + 1,ansy2 + 1);
  187.     }
  188.     else
  189.         printf ("0");
  190.     return 0;
  191. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement