Модуль: Хеширование


Задача

3 /8


Подстроки в строке

Теория Нажмите, чтобы прочитать/скрыть


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

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

Если мы хотим посчитать хэш подотрезка [l;r], то нужно взять хэш на префиксе r и вычесть хэш на префиксе l-1, домноженный на p в степени r-l+1. Почему это так, становится понятным, если расписать значения на префиксах и посмотреть, что происходит. Надеюсь у вас получится, глядя на эту картинку.



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

Тут есть два момента, которые стоит уточнить:
1) Чтобы быстро домножать на p в степени r-l+1, необходимо заранее предпосчитать все возможные степени p по модулю mod.
2) Необходимо помнить, что все вычисления мы производим по модулю mod, а поэтому может получиться так, что после вычитания префиксных хэшей мы получим отрицательное число. Чтобы этого избежать можно всегда прибавлять mod перед вычитанием. Также не забываем после домножений и всех сложений также брать значение по модулю.

В коде это выглядит так:
 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1000003;

// основание и модуль хэширования
ll p, mod;

// префиксный хэш и степени p
ll h[MAXN], pows[MAXN];

// подсчет хэша подотрезка [l;r]
ll get_segment_hash(int l, int r) {
	return (h[r] + mod - h[l - 1] * pows[r - l + 1] % mod) % mod;
}

int main()
{
	// каким то способом получаем p и mod
	
	// предпосчитываем степени p
	pows[0] = 1;
	for (int i = 0; i < MAXN; i++)
	    pows[i] = (pows[i - 1] * p) % mod;
	    
	// 
	// основное решение задачи
	//

	return 0;
}

Задача

Дана строка S = s1s2...sn и множество запросов вида (l1, r1, l2, r2). Для каждого запроса требуется ответить, равны ли подстроки sl1...sr1 и sl2...sr2.


Входные данные:
В первой строке дана строка S (1 <= |S| <= 105), состоящая из строчных латинских букв. 
Во второй строке дано натуральное число q (1 <= q <= 105) - количество запросов.
В следующих q строках дано по 4 натуральных числа - l1, r1, l2, r2 (1 <= l1 <= r1 <= |S|, 1 <=l2 <= r2 <= |S|).

Выходные данные:
Для каждого запроса выведите '+', если подстроки равны, и '-', в противном случае.

Примеры:
 
Входные данные Выходные данные
abacaba
4
1 1 7 7
1 3 5 7
3 4 4 5
1 7 1 7
++-+

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w644
Python1
Комментарий учителя