Как найти хеш подстроки

const int k = 31, mod = 1e9+7;

string s = "abacabadaba";
long long h = 0, m = 1;
for (char c : s) {
    int x = (int) (c - 'a' + 1);
    h = (h + m * x) % mod;
    m = (m * k) % mod;
}

long long h = 0;
for (char c : s) {
    int x = (int) (c - 'a' + 1);
    h = (h * k + x) % mod;
}

const int maxn = 1e5+5;

int p[maxn];
p[0] = 1;

for (int i = 1; i < maxn; i++)
    p[i] = (p[i-1] * k) % mod;

int h[maxn];
h[0] = 0; // h[k] -- хэш префикса длины k

// будем считать, что s это уже последовательность int-ов

for (int i = 0; i < n; i++) 
    h[i+1] = (h[i] + p[i] * s[i]) % mod;

int hash_substring (int l, int r) {
    return (h[r+1] - h[l]) * p[n-l] % mod;
}

Полиномиальные хеши и их применение

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

Введение

Начнем с определения. Пусть у нас есть строка 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⁶⁴, т.е. оно должно быть нечетным). Почему так, я здесь рассказывать не буду — об этом можно почитать в книжках по алгебре. Конечно, неизбежно появляется вероятность коллизии, но она крайне мала, поэтому при решении олимпиадных задач можно ей просто пренебречь.
• Замечание третье: так как все операции мы теперь выполняем по модулю, деление для нас недоступно (точнее, доступно, но писать это довольно неэффективно). Поэтому от него надо избавляться. Делается это довольно просто, способом, который в школе называют «пропорцией»: выражение приводится к общему знаменателю, и вместо деления используется умножение:

  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-функцией строки s называется массив z, i-ый элемент которого равен наидлиннейшему префиксу подстроки, начинающейся с позиции i в строке s, который одновременно является и префиксом всей строки s. Значение z-функции в нулевой позиции будем считать равным длине строки s, хотя некоторые источники принимают его за ноль (но это не критично).

Конечно, есть алгоритм нахождения 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).

Существует алгоритм Дюваля, который позволяет решать эту задачу за 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).

Опять же, существует решение этой задачи за 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]) { ... }

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

Заключение

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

Алгоритм Рабина-Карпа предназначен для поиска подстроки в строке.

Метод хеширования

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

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

Для работы алгоритма потребуется считать хеш подстроки . Делать это можно следующим образом:

Рассмотрим хеш :

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

Вынесем из последней скобки множитель :

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

Отсюда получается следующая формула для :

Однако, как видно из формулы, чтобы уметь считать хеш для всех подстрок начинающихся с , нужно предпосчитать все для . Это займет много памяти. Но поскольку нам нужны только подстроки размером мы можем подсчитать хеш подстроки , а затем пересчитывать хеши для всех за следующим образом:

.

.

Получается : .

Решение

Алгоритм

Алгоритм начинается с подсчета и , а также с подсчета , для ускорения ответов на запрос.

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

Если требуется найти индексы вхождения нескольких образцов, или сравнить две строки выгоднее будет предпосчитать все степени , а также хеши всех префиксов строки .

Псевдокод

Приведем пример псевдокода, который находит все вхождения строки в строку и возвращает массив позиций, откуда начинаются вхождения.

vector<int> rabinKarp (s : string, w : string):
   vector<int> answer
   int n = s.length
   int m = w.length
   int hashS = hash(s[0..m - 1])
   int hashW = hash(w[0..m - 1])
   for i = 0 to n - m
        if hashS == hashW
             answer.add(i)
        hashS = (p * hashS - p * hash(s[i]) + hash(s[i + m])) mod r // r — некоторое большое число, p — некоторое просто число
   return answer

Новый хеш был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что — пустой символ.

Время работы

Изначальный подсчёт хешей выполняется за .

Каждая итерация выполняется за , В цикле всего итераций.

Итоговое время работы алгоритма .

Однако, если требуется исключить ложные срабатывания алгоритма полностью, т.е. придется проверить все полученные позиции вхождения на истинность, то в худшем случае итоговое время работы алгоритма будет .

Сравнение с другими алгоритмами

Преимущества:

• Быстрая скорость работы — , где — длина строки, — длина образца;
• Простая и понятная реализация;

Недостатки:

• Возможно подобрать входные данные так, что количество ложных срабатываний будет недопустимо большим;

См. также

• Наивный алгоритм поиска подстроки в строке
• Поиск наибольшей общей подстроки двух строк с использованием хеширования

Источники информации

• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 3-е издание. Пер. с англ. — М.:Издательский дом «Вильямс», 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страницы 1036–1041.

Hash Function

A Hash function is a function that maps any kind of data of arbitrary size to fixed-size values. The values returned by the function are called Hash Values or digests. There are many popular Hash Functions such as DJBX33A, MD5, and SHA-256. This post will discuss the key features, implementation, advantages and drawbacks of the Polynomial Rolling Hash Function.

Note that if two strings are equal, their hash values should also be equal. But the inverse need not be true.

The polynomial rolling hash function

Polynomial rolling hash function is a hash function that uses only multiplications and additions. The following is the function:

or simply,

Where

Below is the implementation of the Polynomial Rolling Hash Function

Hash of geeksforgeeks is 609871790

Time Complexity: O(N)

Auxiliary Space: O(1)

Collisions in Polynomial Rolling Hash

Since the output of the Hash function is an integer in the range , there are high chances for two strings producing the same hash value.

For instance, the strings  and  produce the same hash value for  and .

Also, the strings  and   produce the same hash value for  and .

We can guarantee a collision within a very small domain. Consider a set of strings, , consisting of only lower-case letters, such that the length of any string in  doesn’t exceed .

We have . Since the range of the Hash Function is , one-one mapping is impossible. Hence, we can guarantee a collision by arbitrarily generating two strings whose length doesn’t exceed .

Collision Resolution

We can note that the value of  affects the chances of collision. We have seen that the probability of collision is . We can increase the value of  to reduce the probability of collision. But that affects the speed of the algorithm. Larger the value of , the slower the algorithm. Also, some languages (C, C++, Java) have a limit on the size of the integer. Hence, we can’t increase the value of  to a very large value.

Then how can we minimise the chances of a collision?

Note that the hash of a string depends on two parameters:  and .

We have seen that the strings  and  produce the same hash value for  and . But for  and , they produce different hashes.

Observation:

If two strings produce the same hash values for a pair , they will produce different hashes for a different pair, .

Strategy:

We cannot, however, nullify the chances of collision because there are infinitely many strings. But, surely, we can reduce the probability of two strings colliding.

We can reduce the probability of collision by generating a pair of hashes for a given string. The first hash is generated using  and , while the second hash is generated using  and .

Why will this work?

We are generating two hashes using two different modulo values,  and . The probability of a collision is now . Since both  and  are greater than , the probability that a collision occurs is now less than  which is so much better than the original probability of collision, .

Below is the implementation for the same

Hash values of geeksforgeeks are: (609871790, 642799661)

Time Complexity: O(N)

Auxiliary Space: O(1)

Features of Polynomial rolling hash function

Calculation of Hashes of any substring of a given string in 

Note that computing the hash of the string S will also compute the hashes of all of the prefixes. We just have to store the hash values of the prefixes while computing. Say text{hash[i]} denotes the hash of the prefix text{S[0…i]}, we have

This allows us to quickly compute the hash of the substring  in  provided we have powers of  ready.

The behaviour of the hash when a character is changed

Recall that the hash of a string  is given by

Say, we change a character  at some index  to some other character . How will the hash change?

If  denotes the hash value before changing and  is the hash value after changing, then the relation between them is given by

Therefore, queries can be performed very quickly instead of recalculating the hash from beginning, provided we have the powers of  ready.

A more elegant implementation is provided below. 

In the above implementation, we are computing the inverses of powers of $p$ in linear time.

Applications:

Consider this problem: Given a sequence S of N strings and Q queries. In each query, you are given two indices, i and j, your task is to find the length of the longest common prefix of the strings S[i] and S[j].

Before getting into the approach to solve this problem, note that the constraints are:

Using Hashing, the problem can be solved in O(N + Q/log|S|_{max}). The approach is to compute hashes for all the strings in O(N) time, Then for each query, we can binary search the length of the longest common prefix using hashing. The implementation for this approach is provided below.

Input:
5 4
geeksforgeeks geeks hell geeksforpeaks hello
1 2
1 3
3 5
1 4

Expected Output:
5
0
4
8

Last Updated :
10 Apr, 2023

Like Article

Save Article