Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*описание tl10-решения задачи №1486-timus:
- 1. делам преподсчет "префиксов" для квадратов из букв, чтобы потом можно было найти хэш от любого квадрта за О(1)
- 2. Бинарный алгоритмом проходимся по длине стороны квадрата, что нужно найти
- 3. Осуществляем перебор всех квадратов (со стороной длину которого мы находим в пункте 2)
- 4. при этом все сгенерированные хэши попадают в дерево поиска tree666 для того чтобы можно было проверять за O(log N * M) есть ли этот хэш.
- 5. если хэш нашли то просто выходим
- 6. если одинаковые хэши не найдены, то отчищаем дерево так как эти хэши уже не нужны
- */
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <set>
- #include <map>
- using namespace std;
- #define ULL unsigned long long
- #define US unsigned short
- int p = 29;
- int q = 31;
- int ansx = 0,ansy = 0;
- int ansx2 = 0,ansy2 = 0;
- ULL p_powx[500] = {0};
- ULL p_powy[500] = {0};
- template<class T>
- struct node//дерево нужно для поиска одинаковых хэшей за О(log n * m)
- {
- T value;//хэш
- US l,r; //координаты квадрта
- node *pleft,*pright;
- node() : pleft(0),pright(0){};
- };
- template<class T>
- void addToTree (node<T> **pF,T x,US l,US r)
- {
- if(!(*pF))
- {
- *pF = new node<T>();
- (*pF)->value = x;
- (*pF)->l = l;
- (*pF)->r = r;
- }
- else
- {
- if((*pF)->value > x)
- addToTree (&((*pF)->pleft),x,l,r);
- else
- addToTree (&((*pF)->pright),x,l,r);
- }
- }
- template<class T>
- bool findInsideTree (node<T>* p,T x) {//поиск одинаковых хэшей
- if(!p)
- return false;
- if(p->value == x)
- {//нашли одинаковые хэши
- ansx = p->l;//запомнили координаты
- ansy = p->r;
- return true;
- }
- if(x < p->value)
- return findInsideTree (p->pleft,x);
- else
- return findInsideTree (p->pright,x);
- }
- template<class T>
- void deltree (node<T>* p) {//удаление дерева
- if (!p->pleft && !p->pright)
- {
- p->value = 0;
- delete p;
- }
- else if (!p->pleft && p->pright)
- {
- deltree (p->pright);
- p->value = 0;
- delete p;
- }
- else if (p->pleft && !p->pright)
- {
- deltree (p->pleft);
- p->value = 0;
- delete p;
- }
- else if(p->pleft && p->pright)
- {
- deltree (p->pleft);
- deltree (p->pright);
- delete p;
- }
- p = NULL;
- }
- node<ULL> *tree666;//обычно двоичное дерево где будут храиться хэши для быстрого поиска
- ULL pref[500][500] = {0};//префиксы квадратов
- int N,M;
- bool find_common_squar (int m)//поиск одинаковы квадратов или хэшей
- {
- int indgl = 0;
- int rlt = m - 1;
- for (int i = 0; i < N - rlt; i++)
- {
- for (int j = 0; j < M - rlt; j++)
- {//за 1 находим хэш квадрата заключенного между i,j i + m,j + m
- ULL hash = pref[rlt + i][rlt + j];
- if (i && j)
- hash -= (pref[i - 1][rlt + j] + pref[rlt + i][j - 1] - pref[i - 1][j - 1]);
- else if (i)
- hash -= pref[i - 1][rlt + j];
- else if (j)
- hash -= pref[rlt + i][j - 1];
- hash *= p_powx[N - rlt - i - 1] * p_powy[M - rlt - j - 1];
- if (findInsideTree (tree666,hash))//поиск
- {//нашли одинаковые хэши
- ansx2 = i;
- ansy2 = j;
- return true;
- }
- addToTree (&tree666,hash,i,j);//добавить хэш в дерево поиска
- }
- }
- deltree (tree666);//отчистить дерево поиска так как эти хэши уже не нужны
- tree666 = NULL;
- return false;
- }
- int main()
- {
- //freopen("input.txt","r",stdin);
- //freopen("output.txt","w",stdout);
- int n,m;
- scanf ("%d%d\n",&n,&m);
- p_powx[0] = 1;
- for (int i = 1; i < n; i++)
- p_powx[i] = p_powx[i - 1] * p;//табличка по первому простому числу
- N = n;
- p_powy[0] = 1;
- for (int i = 1; i < m; i++)
- p_powy[i] = p_powy[i - 1] * q;//табличка по второу простому числу
- M = m;
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < m; j++)
- {
- char ch;
- scanf ("%c",&ch);
- pref[i][j] = (ch - 'a' + 1) * p_powx[i] * p_powy[j]; //квадратные префиксы
- if (i && j)
- {
- pref[i][j] += (pref[i][j - 1] + pref[i - 1][j] - pref[i - 1][j - 1]);//убрать лишние квадрта, или выделить нужный квадрат
- }
- else if (i)
- {//тоже
- pref[i][j] += pref[i - 1][j];
- }
- else if (j)
- {//тоже
- pref[i][j] += pref[i][j - 1];
- }
- }
- scanf ("\n");
- }
- int L = 1;
- int R = min (n,m);
- int ind = 1;
- while (L < R)//бинарный поиск по длине стороны квадрата
- {
- int mid = (L + R) / 2;
- if(find_common_squar (mid))
- {
- ind = mid;
- L = mid + 1;
- }
- else
- R = mid;
- }
- if(find_common_squar (L))
- {
- printf ("%d\n",L);
- printf ("%d %d\n",ansx + 1,ansy + 1);
- printf ("%d %d",ansx2 + 1,ansy2 + 1);
- }
- else if(ind != 1)
- {
- printf ("%d\n",ind);
- printf ("%d %d\n",ansx + 1,ansy + 1);
- printf ("%d %d",ansx2 + 1,ansy2 + 1);
- }
- else
- printf ("0");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement