Хеширование матриц

Задача

Вам дана матрица $M_{i, j}$ размера $H \times W$, состоящая из чисел, и $Q$ запросов вида равны ли подматрицы $M_{x_1 \leq i \leq x_2, y_1 \leq j \leq y_2}$ и $M_{x_3 \leq i \leq x_4, y_3 \leq j \leq y_4}$.

Решение за $O(\text{число строк в запросе})$

Давайте посмотрим на матрицу как на набор строк. Тогда сравнивать подматрицы это то же самое, что сравнивать несколько раз подстроки на равенство, а это мы уже умеем делать хешами.

Решение за $O(1)$

Давайте обобщим идею полиномиального хеширования строк на матрицы. Для этого нам понадобится два разных $p ~- p_h$ и $p_v$.

Положим теперь $$ h\Big(M_{x_1 \leq i \leq x_2, y_1 \leq j \leq y_2}\Big) = \Big[\sum_{x_1 \leq i \leq x_2, y_1 \leq j \leq y_2} M_{i, j} \times p_h^{i} \times p_v^{j}\Big] \times \underbrace{ p_h^{x_1} \times p_v^{y_1}}_{\substack{\text{поправка, учитывающая сдвиг от (0, 0)} \\ \text{ниже мы поймём, зачем она нужна}}}. $$

Предподсчёт за $O(n^2)$

Предподсчитаем хеши для всех угловых подматриц (обобщение понятия префикс строки). Сперва заметим, что для всех угловых подматриц, которые содержат только первую строку, определение хеша совпадает с определением полиномиального хеша для строки, а значит такие хеши мы умеем предподсчитать за линию. Аналогично с угловыми подматрицами, которые содержат только первый столбец.

Теперь заметим, что для всех остальных подматриц $h(x, y) = h(x-1, y) + h(x, y-1) - h(x-1, y-1) + M_{x, y}p_h^x p_v^y$. Значит, для всех $H \times W$ угловых подматриц мы умеем считать хеш за $\underbrace{O(H) + O(W)}_{\text{хеши первой строки и столбца}} + (H-1) \times (W-1) \times O(1) = O(H \times W)$.

Проверка на равенство за $O(1)$

Заметим, что $h(x_1, y_1, x_2, y_2) = h(x_2, y_2) - h(x_1 - 1, y_2) - h(x_2, y_1 - 1) + h(x_1 - 1, y_1 - 1)$. Однако, это стало возможно только благодаря той добавке, которую мы добавили в определение хеша подматрицы, поэтому теперь, чтобы сравнить две подматрицы, надо хеш той из них, у которой $x$-координата левого верхнего угла меньше, домножить на $p_h^{|x-x'|}$, а хеш той, у которой $y$-координата левого верхнего угла меньше, домножить на $p_v^{|y-y'|}$ (заметьте, что это может быть одна и та же матрица). Теперь, если получившиеся хеши равны, то мы можем с большой долей уверенности говорить, что исходные матрицы тоже были равны.

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex