Алгоритмы хэширования в задачах на строки

Алгоритмы хэширования строк помогают решить очень много задач. Но у них есть большой недостаток: что чаще всего они не 100%-ны, поскольку есть множество строк, хэши которых совпадают. Другое дело, что в большинстве задач на это можно не обращать внимания, поскольку вероятность совпадения хэшей всё-таки очень мала.

Определение хэша и его вычисление

Один из лучших способов определить хэш-функцию от строки S следующий:

h(S)  =  S[0]  +  S[1] * P  +  S[2] * P^2  +  S[3] * P^3  +  ...  +  S[N] * P^N

где P - некоторое число.

Разумно выбирать для P простое число, примерно равное количеству символов во входном алфавите. Например, если строки предполаются состоящими только из маленьких латинских букв, то хорошим выбором будет P = 31. Если буквы могут быть и заглавными, и маленькими, то, например, можно P = 53.

Во всех кусках кода в этой статье будет использоваться P = 31.

Само значение хэша желательно хранить в самом большом числовом типе - int64, он же long long. Очевидно, что при длине строки порядка 20 символов уже будет происходить переполнение значение. Ключевой момент - что мы не обращаем внимание на эти переполнения, как бы беря хэш по модулю 2^64.

Пример вычисления хэша, если допустимы только маленькие латинские буквы:

const int p = 31;
long long hash = 0, p_pow = 1;
for (size_t i=0; i<s.length(); ++i)
{
	// желательно отнимать 'a' от кода буквы
	// единицу прибавляем, чтобы у строки вида 'aaaaa' хэш был ненулевой
	hash += (s[i] - 'a' + 1) * p_pow;
	p_pow *= p;
}

В большинстве задач имеет смысл сначала вычислить все нужные степени P в каком-либо массиве.

Пример задачи. Поиск одинаковых строк

Уже теперь мы в состоянии эффективно решить такую задачу. Дан список строк S[1..N], каждая длиной не более M символов. Допустим, требуется найти все повторяющиеся строки и разделить их на группы, чтобы в каждой группе были только одинаковые строки.

Обычной сортировкой строк мы бы получили алгоритм со сложностью O (N M log N), в то время как используя хэши, мы получим O (N M + N log N).

Алгоритм. Посчитаем хэш от каждой строки, и отсортируем строки по этому хэшу.

vector<string> s (n);
// ... считывание строк ...

// считаем все степени p, допустим, до 10000 - максимальной длины строк
const int p = 31;
vector<long long> p_pow (10000);
p_pow[0] = 1;
for (size_t i=1; i<p_pow.size(); ++i)
	p_pow[i] = p_pow[i-1] * p;

// считаем хэши от всех строк
// в массиве храним значение хэша и номер строки в массиве s
vector < pair<long long, int> > hashes (n);
for (int i=0; i<n; ++i)
{
	long long hash = 0;
	for (size_t j=0; j<s[i].length(); ++j)
		hash += (s[i][j] - 'a' + 1) * p_pow[j];
	hashes[i] = make_pair (hash, i);
}

// сортируем по хэшам
sort (hashes.begin(), hashes.end());

// выводим ответ
for (int i=0, group=0; i<n; ++i)
{
	if (i == 0 || hashes[i].first != hashes[i-1].first)
		cout << "\nGroup " << ++group << ":";
	cout << ' ' << hashes[i].second;
}

Хэш подстроки и его быстрое вычисление

Предположим, нам дана строка S, и даны индексы I и J. Требуется найти хэш от подстроки S[I..J].

По определению имеем:

H[I..J]  =  S[I]  +  S[I+1] * P  +  S[I+2] * P^2  +  ...  + S[J] * P^(J-I)

откуда:

H[I..J] * P[I]  =  S[I] * P[I]  +  ...  +  S[J] * P[J],
H[I..J] * P[I]  =  H[0..J]  -  H[0..I-1]

Полученное свойство является очень важным.

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

Единственная возникающая проблема - это то, что нужно уметь делить на P[I]. На самом деле, это не так просто. Поскольку мы вычисляем хэш по модулю 2^64, то для деления на P[I] мы должны найти к нему обратный элемент в поле (например, с помощью Расширенного алгоритма Евклида), и выполнить умножение на этот обратный элемент.

Впрочем, есть и более простой путь. В большинстве случаев, вместо того чтобы делить хэши на степени P, можно, наоборот, умножать их на эти степени.

Допустим, даны два хэша: один умноженный на P[I], а другой - на P[J]. Если I < J, то умножим перый хэш на P[J-I], иначе же умножим второй хэш на P[I-J]. Теперь мы привели хэши к одной степени, и можем их спокойно сравнивать.

Например, код, который вычисляет хэши всех префиксов, а затем за O (1) сравнивает две подстроки:

string s;  int i1, i2, len; // входные данные

// считаем все степени p
const int p = 31;
vector<long long> p_pow (s.length());
p_pow[0] = 1;
for (size_t i=1; i<p_pow.size(); ++i)
	p_pow[i] = p_pow[i-1] * p;

// считаем хэши от всех префиксов
vector<long long> h (s.length());
for (size_t i=0; i<s.length(); ++i)
{
	h[i] = (s[i] - 'a' + 1) * p_pow[i];
	if (i)  h[i] += h[i-1];
}

// получаем хэши двух подстрок
long long h1 = h[i1+len-1];
if (i1)  h1 -= h[i1-1];
long long h2 = h[i2+len-1];
if (i2)  h2 -= h[i2-1];

// сравниваем их
if (i1 < i2 && h1 * p_pow[i2-i1] == h2 ||
	i1 > i2 && h1 == h2 * p_pow[i1-i2])
	cout << "equal";
else
	cout << "different";

Применение хэширования

Вот некоторые типичные применения хэширования:

Алгоритм Рабина-Карпа поиска подстроки в строке за O (N)
Определение количества различных подстрок за O (N^2 log N) (см. ниже)
Определение количества палиндромов внутри строки

Определение количества различных подстрок

Пусть дана строка S длиной N, состоящая только из маленьких латинских букв. Требуется найти количество различных подстрок в этой строке.

Для решения переберём по очереди длину подстроки: L = 1 .. N.

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

Реализация:

string s; // входная строка
int n = (int) s.length();

// считаем все степени p
const int p = 31;
vector<long long> p_pow (s.length());
p_pow[0] = 1;
for (size_t i=1; i<p_pow.size(); ++i)
	p_pow[i] = p_pow[i-1] * p;

// считаем хэши от всех префиксов
vector<long long> h (s.length());
for (size_t i=0; i<s.length(); ++i)
{
	h[i] = (s[i] - 'a' + 1) * p_pow[i];
	if (i)  h[i] += h[i-1];
}

int result = 0;

// перебираем длину подстроки
for (int l=1; l<=n; ++l)
{
	// ищем ответ для текущей длины

	// получаем хэши для всех подстрок длины l
	vector<long long> hs (n-l+1);
	for (int i=0; i<n-l+1; ++i)
	{
		long long cur_h = h[i+l-1];
		if (i)  cur_h -= h[i-1];
		// приводим все хэши к одной степени
		cur_h *= p_pow[n-i-1];
		hs[i] = cur_h;
	}

	// считаем количество различных хэшей
	sort (hs.begin(), hs.end());
	hs.erase (unique (hs.begin(), hs.end()), hs.end());
	result += (int) hs.size();
}

cout << result;