Здравствуй. Сегодня я напишу, как можно использовать полиномиальные хеши (далее просто хеши) при решении различных алгоритмических задач.

Введение

Начнем с определения. Пусть у нас есть строка s_0..n-1. Полиномиальным хешем этой строки называется число h = hash(s_0..n-1) = s₀ + ps₁ + p²s₂ +… + p^n-1s_n-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а s_i — код i-ого символа строки s (почти во всех современных языках он записывается s[i]).

Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны. Поэтому основная операция, которую позволяют выполнять хеши — быстрое сравнение двух подстрок на равенство. Конечно, чтобы сравнить 2 строки, мы можем написать подобную функцию (будем считать, что длины строк s и t совпадают и равны n):

boolean equals(char[] s, char[] t) {
	for (int i = 0; i < n; i++)
		if (s[i] != t[i]) {
			return false;
		}
	}
	return true;
}

Однако в худшем случае эта функция обязана проверить все символы, что дает асимптотику O(n).

Сравнение строк с помощью хешей

Теперь посмотрим, как справляются с этой задачей хеши. Так как хеш — это всего лишь число, для их сравнения нам потребуется O(1) времени. Правда, для того, чтобы посчитать хеш одной подстроки наивным способом, требуется O(n) времени. Поэтому потребуется немного повозиться с математическими формулами и научиться находить за O(n) хеши сразу всех подстрок. Давайте сравним подстроки s_L..R и t_X..Y (одинаковой длины). Пользуясь определением хеша, мы можем записать:

s_L + ps_L+1 +… + p^R-L-1s_R-1 + p^R-Ls_R = t_X + pt_X+1 +… + p^Y-X-1t_Y-1 + p^Y-Xt_Y

Проведем небольшие преобразования в левой части (в правой части все будет происходить аналогично). Запишем хеш подстроки s_0..R, он нам понадобится:

hash(s_0..R) = s₀ + ps₁ +… + p^L-1s_L-1 + p^Ls_L + p^L+1s_L+1 +… + p^R-1s_R-1 + p^Rs_R

Разобьем это выражение на две части…

hash(s_0..R) = (s₀ + ps₁ +… + p^L-1s_L-1) + (p^Ls_L + p^L+1s_L+1 +… + p^R-1s_R-1 + p^Rs_R)

… и вынесем из второй скобки множитель p^L:

hash(s_0..R) = (s₀ + ps₁ +… + p^L-1s_L-1) + p^L(s_L + ps_L+1 +… + p^R-L-1s_R-1 + p^R-Ls_R)

Выражение в первой скобке есть не что иное, как хеш подстроки s_0..L-1, а во второй — хеш нужной нам подстроки s_L..R. Итак, мы получили, что:

hash(s_0..R) = hash(s_0..L-1) + p^Lhash(s_L..R)

Отсюда вытекает следующая формула для hash(s_L..R):

hash(s_L..R) = (1 / p^L)(hash(s_0..R) — hash(s_0..L-1))

Аналогично, для второй нашей подстроки будет выполнено равенство hash(t_X..Y) = (1 / p^X)(hash(t_0..Y) — hash(t_0..X-1)).

Внимательно глядя на эти формулы, можно заметить, что для вычисления хеша любой подстроки нам необходимо знать лишь хеши префиксов этой строки s_0..0, s_0..1, ..., s_0..n-2, s_0..n-1. А, так как хеш каждого следующего префикса выражается через хеш предыдущего, их несложно посчитать линейным проходом по строке. Все сразу за O(n) времени. Степени числа p тоже надо заранее предпросчитать и сохранить в массиве.

Пример кода:

// сохраняем в массиве степени числа p, которые нам могут понадобиться
pow[0] = 1;
for (int i = 1; i <= MAX; i++) {
	pow[i] = pow[i - 1] * p;
}

// считаем хеши префиксов строки s
hs[0] = s[0];
for (int i = 1; i < n; i++) {
	hs[i] = hs[i - 1] + pow[i] * s[i];
}

// считаем хеши префиксов строки t
ht[0] = t[0];
for (int i = 1; i < m; i++) {
	ht[i] = ht[i - 1] + pow[i] * t[i];
}

Казалось бы, мы теперь во всеоружии и умеем сравнивать 2 любые подстроки за O(1). Но не все так просто: математические формулы нуждаются в некоторой доработке. К примеру, подобный код:

if ((hs[R] - hs[L - 1]) / pow[L] == (ht[Y] - ht[X - 1]) / pow[X]) { ... }

работать не будет.

• Замечание первое: L (или X) может оказаться равным нулю, и при вычислении hs[L - 1] произойдет выход за границы массива. Однако если L равно нулю, то интересующий нас хеш подстроки s_L..R хранится в точности в hs[R]. Поэтому правильнее вместо hs[L - 1] писать так:

  L == 0 ? 0 : hs[L - 1]

  .

• Замечание второе: даже тип long содержит всего 64 бита (я использую Java), а наши строки могут быть длиной в несколько тысяч, и при вычислении хешей неизбежно произойдет переполнение. Эту проблему решить проще всего: надо закрыть на нее глаза. Ну, или почти закрыть: хеши у нас будут считаться, по сути, по модулю 2⁶⁴ (и поэтому не потребуется выполнять операции взятия остатка от деления — красота!). Число p для их подсчета должно быть, во-первых, больше кода самого большого символа в строках, а во-вторых, взаимно простым с модулем (в нашем случае — с 2⁶⁴, т.е. оно должно быть нечетным). Почему так, я здесь рассказывать не буду — об этом можно почитать в книжках по алгебре. Конечно, неизбежно появляется вероятность коллизии, но она крайне мала, поэтому при решении олимпиадных задач можно ей просто пренебречь.
• Замечание третье: так как все операции мы теперь выполняем по модулю, деление для нас недоступно (точнее, доступно ^[1], но писать это довольно неэффективно). Поэтому от него надо избавляться. Делается это довольно просто, способом, который в школе называют «пропорцией»: выражение приводится к общему знаменателю, и вместо деления используется умножение:

  if ((hs[R] - (L == 0 ? 0 : hs[L - 1])) * pow[X] ==
      (ht[Y] - (X == 0 ? 0 : ht[X - 1])) * pow[L]) { ... }
  

Теперь мы более подробно рассмотрим задачи, где можно применять хеши.

Задачи, решаемые с помощью хешей

1. Сравнение подстрок

Первое, и главное, применение, как уже было сказано, это быстрое сравнение двух подстрок — на нем основываются все остальные алгоритмы с хешами. Код в прошлом разделе довольно громоздкий, поэтому я напишу более удобный код, который будет использоваться в дальнейшем.
Следующая функция вычисляет хеш подстроки s_L..R, умноженный на p^L:

long getHash(long[] h, int L, int R) {
	long result = h[R];
	if (L > 0) result -= h[L - 1];
	return result;
}

Теперь сравнение двух подстрок мы выполняем следующей строчкой:

if (getHash(hs, L, R) * pow[X] == getHash(ht, X, Y) * pow[L]) { ... }

Умножение на степени числа p можно назвать «приведением к одной степени». Первый хеш был умножен на p^L, а второй — на p^X — значит, чтобы сравнение происходило корректно, их надо домножить на недостающий множитель.
Примечание: имеет смысл сначала проверить, совпадают ли длины подстрок. Если нет, то строки в принципе не могут быть равны, и тогда можно не проверять вышезаписанное условие.

2. Поиск подстроки в строке за O(n + m)

Хеши позволяют искать подстроку в строке за асимптотически минимальное время. Это делает так называемый алгоритм Рабина-Карпа.
Пусть есть строка s длины n, в которой мы хотим найти все вхождения строки t длины m. Найдем хеш строки t (всей строки целиком) и хеши всех префиксов строки s, а затем будем двигаться по строке s окном длины m, сравнивая подстроки s_i..i+m-1.
Код:

// считаем хеш строки t
long ht = t[0];
for (int i = 1; i < m; i++) {
	ht += pow[i] * t[i];
}

// проверяем все позиции
for (int i = 0; i + m <= n; i++) {
	if (getHash(h, i, i + m - 1) == ht * pow[i]) {
		// обнаружено совпадение на позиции i
	}
}

3. Нахождение z-функции за O(n log n)

Z-функцией ^[2] строки s называется массив z, i-ый элемент которого равен наидлиннейшему префиксу подстроки, начинающейся с позиции i в строке s, который одновременно является и префиксом всей строки s. Значение z-функции в нулевой позиции будем считать равным длине строки s, хотя некоторые источники принимают его за ноль (но это не критично).

Конечно, есть алгоритм ^[3] нахождения z-функции за O(n). Но когда его не знаешь или не помнишь (а алгоритм довольно громоздкий), на помощь приходят хеши.

Идея следующая: для каждого i = 0, 1, ..., n-1 будем искать z_i бинарным поиском, т.е. на каждой итерации сокращая интервал возможных значений вдвое. Это корректно, потому что равенство s_0..k-1 = s_i..i+k-1 обязательно выполняется для всех k, меньших z_i, и обязательно не выполняется для больших k.

Код:

int[] z = new int[n];
for (int i = 0; i < n; i++) {
	int left = 1, right = n - i; // текущий интервал значений
	while (left <= right) {
		// находим middle - середину интервала
		int middle = (left + right) / 2;
		// и проверяем, совпадают ли подстроки s[0..middle-1] и s[i..i+middle-1]
		if (getHash(h, 0, middle - 1) * pow[i] == getHash(h, i, i + middle - 1)) {
			// если совпадают, то ответ как равен минимум middle, и надо проверить большие значения
			z[i] = middle;
			left = middle + 1;
		} else {
			// если не совпадают, надо проверить меньшие значения
			right = middle - 1;
		}
	}
}

4. Поиск лексикографически минимального циклического сдвига строки за O(n log n).

Существует алгоритм Дюваля ^[4], который позволяет решать эту задачу за O(n), однако я знаю некоторых довольно сильных олимпиадных программистов, которые так и не разобрались в нем. Пока они будут в нем разбираться, мы снова применим хеши.

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

Код:

int bestPos = 0;
for (int i = 1; i < n; i++) {
	int left = 1, right = n, length = 0;
	// находим length - длину максимального общего префикса
	while (left <= right) {
		int middle = (left + right) / 2;
		if (getHash(h, bestPos, bestPos + middle - 1) * pow[i] ==
		    getHash(h, i, i + middle - 1) * pow[bestPos]) {
			length = middle;
			left = middle + 1;
		} else {
			right = middle - 1;
		}
	}
	// сравниваем следующий за общим префиксом символ и обновляем ответ
	// если длина этого префикса равна n,
	// то текущий циклический сдвиг совпадает с минимальным,
	// и ответ обновлять не нужно
	if (length < n && s[i + length] < s[bestPos + length]) {
		bestPos = i;
	}
}

Примечание: по сути, внутри цикла for написан компаратор, сравнивающий лексикографически два циклических сдвига. Используя его, можно за O(n log² n) отсортировать все циклические сдвиги.

5. Поиск всех палиндромов в строке за O(n log n).

Опять же, существует решение ^[5] этой задачи за O(n). И опять мы будем решать ее с помощью хешей.

Подстрока s_L..R называется палиндромом, если s_L = s_R, s_L+1 = s_R-1, и т.д. Если выражаться русским языком, то это означает, что она читается одинаково как слева направо, так и справа налево.

Возможно, вы уже знаете или догадались, при чем тут хеши. Помимо массива h[], содержащего хеши для подстрок s_0..0, s_0..1, ..., s_0..n-2, s_0..n-1, посчитаем второй массив rh[] (для «перевернутой» строки), который будем обходить справа налево. Он будет содержать соответственно хеши s_0..n-1, s_1..n-1, ..., s_n-2..n-1, s_n-1..n-1:

rh[n - 1] = s[n - 1];
for (int i = n - 2, j = 1; i >= 0; i--, j++) {
	rh[i] = rh[i + 1] + pow[j] * s[i];
}

Должно уже быть понятно, как за O(1) определять, является ли строка палиндромом. Я напишу функцию getRevHash(), аналогичную getHash(), а потом приведу необходимое условие сравнения. Вы можете самостоятельно убедиться в правильности этого выражения, проделав математические выкладки, подобные тем, что приводились в начале статьи.

long getRevHash(long[] rh, int L, int R) {
	long result = rh[L];
	if (R < n - 1) result -= rh[R + 1];
	return result;
}

boolean isPalindrome(long[] h, long[] rh, long[] pow, int L, int R) {
	return getHash(h, L, R) * pow[n - R - 1] == getRevHash(rh, L, R) * pow[L];
}

Теперь рассмотрим позицию i в строке. Пусть существует палиндром нечетной длины d с центром в позиции i (в случае четной длины — с центром между позициями i-1 и i). Если обрезать с его краев по одному символу, он останется палиндромом. И так можно продолжать, пока его длина не станет равной нулю.
Таким образом, нам достаточно для каждой позиции хранить 2 значения: сколько существует палиндромов нечетной длины с центром в позиции i, и сколько существует палиндромов четной длины с центром между позициями i-1 и i. Обратите внимание, что эти 2 значения абсолютно независимы друг от друга, и обрабатывать их надо отдельно.

Применим, как и ранее, бинарный поиск:

int[] oddCount = new int[n];
for (int i = 0; i < n; i++) {
	int left = 1, right = min(i + 1, n - i);
	while (left <= right) {
		int middle = (left + right) / 2;
		if (isPalindrome(h, rh, pow, i - middle + 1, i + middle - 1)) {
			oddCount[i] = middle;
			left = middle + 1;
		} else {
			right = middle - 1;
		}
	}
}

int[] evenCount = new int[n];
for (int i = 0; i < n; i++) {
	int left = 1, right = min(i, n - i);
	while (left <= right) {
		int middle = (left + right) / 2;
		if (isPalindrome(h, rh, pow, i - middle, i + middle - 1)) {
			evenCount[i] = middle;
			left = middle + 1;
		} else {
			right = middle - 1;
		}
	}
}

Теперь можно, к примеру, найти общее количество всех палиндромов в строке, или длину максимального палиндрома. Длина максимального нечетного палиндрома с центром в позиции i считается как 2 * oddCount[i] - 1, а максимального четного палиндрома — 2 * evenCount[i].
Еще раз напомню, что нужно быть внимательнее с палиндромами четной и нечетной длины — как правило, их надо обрабатывать независимо друг от друга.

Хеши в матрицах

Наконец, рассмотрим более изощренные применения хешей. Теперь наше пространство будет двумерным, и сравнивать мы будем подматрицы. К счастью, хеши очень хорошо обобщаются на двумерный случай (трехмерных и более я не встречал).

Теперь вместо числа p и массива pow у нас будут два различных числа p, q и два массива pow1, pow2: по одному числу и по одному массиву в каждом направлении: по вертикали и горизонтали.

Хешем матрицы a_{0..n-1, 0..m-1} будем называть сумму по всем i = 0, ..., n-1, j = 0,..., m-1 величин pⁱq^ja_ij.

Теперь научимся считать хеши подматриц, содержащих левый верхний элемент a₀₀. Очевидно, что hash(a_{0..0, 0..0}) = a₀₀. Почти так же очевидно, что для всех j = 1,..., m-1 hash(a_{0..0, 0..j}) = hash(a_{0..0, 0..j-1}) + q^ja_0j, для всех i = 1,..., n-1 hash(a_{0..i, 0..0}) = hash(a_{0..i-1, 0..0}) + pⁱa_i0. Это напрямую вытекает из одномерного случая.

Как посчитать хеш подматрицы a_{0..i, 0..j}? Можно догадаться, что hash(a_{0..i, 0..j}) = hash(a_{0..i-1, 0..j}) + hash(a_{0..i, 0..j-1}) — hash(a_{0..i-1, 0..j-1}) + pⁱq^ja_ij. Эту формулу можно получить из следующих соображений: сложим все слагаемые (хеш, напомню, это сумма нескольких слагаемых), составляющие хеш подматриц a_{0..i-1, 0..j} и a_{0..i, 0..j-1}. При этом мы два раза учли слагаемые, составляющие подматрицу a_{0..i-1, 0..j-1}, так что вычтем их, чтобы они учитывались один раз. Теперь не хватает только элемента a_ij, умноженного на соответствующие степени p и q.

Примерно из тех же соображений, что и в первой части статьи (вы уже заметили причастность формулы включений-исключений?) строится функция для вычисления хеша произвольной подматрицы a_{x1..x2, y1..y2}:

long getMatrixHash(long[][] h, int x1, int x2, int y1, int y2) {
	long result = h[x2][y2];
	if (x1 > 0) result -= h[x1 - 1][y2];
	if (y1 > 0) result -= h[x2][y1 - 1];
	if (x1 > 0 && y1 > 0) result += h[x1 - 1][y1 - 1];
	return result;
}

Эта функция возвращает хеш подматрицы a_{x1..x2, y1..y2}, умноженный на величину p^x1q^y1.

А сравнение двух подматриц a_{ax1..ax2, ay1..ay2} и a_{bx1..bx2, by1..by2} выполняется с помощью следующего выражения:

if (getMatrixHash(h, ax1, ax2, ay1, ay2) * pow1[bx1] * pow2[by1] ==
    getMatrixHash(h, bx1, bx2, by1, by2) * pow1[ax1] * pow2[ay1]) { ... }

Хешами также можно решать задачи, связанные с нахождением самой большой симметричной подматрицы и похожие на них. Причем я не знаю сравнимых с хешами по скорости и простоте алгоритмов, выполняющих эту работу. Здесь используются те же принципы, что и при поиске палиндромов в одномерном случае (т.е. считать «реверснутые» хеши справа налево и снизу вверх, проводить бинпоиск отдельно для подматриц четной и нечетной длины). Предлагаю попробовать решить эту задачу самостоятельно — эта статья вам поможет!

Заключение

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

Автор: bluesky