Вместо hash_set с некоторых пор рекомендуется использовать

unordered_set (тоже использует хеш-таблицу)

А вместо hash_map - unordered_map


Хеш-таблица
{noformat}
hash_set <type> h;
hash_multiset <type> h; - может хранить несколько одинаковых элементов

void insert(type) - добавление элемента в хеш-таблицу
hash_set <type>::iterator find(<type>) - возвращает итератор указывающий на элемент,
который передаётся в качестве параметра
Если такого элемента не существует, то результат будет
равен значению метода end() для соотвествующей хеш-таблицы
Изменять значение по этому итератору нельзя.
void erase(hash_set <type>::iterator) - удаляет значение, на которое указывает итератор,
из хеш-таблицы
void clear() - очищает содержимое хеш-таблицы

Хеш-словарь

hash_map <int,string> hm;
hash_map <int,string>::iterator it;
hm.insert(pair <int, string> (204888678, "gu"));
hm.insert(pair <int, string> (666666666, "unknown"));
it = hm.find(666666666);
cout << it->second);

int i=204888678; - Обращение к существующему элементу
cout << hm[i];

hm[123456789]="somebody"; - Добавление элемента в hash_map;

{noformat}

Хеш-функция


15_FebS. CENSOR_SILVER
http://dl.gsu.by/task.jsp?nid=1421155&cid=15

Фермер Джон купил подписку журнала Good Hooveskeeping для своих коров, теперь им есть что почитать. К несчастью, последний номер содержит довольно неподходящую статью, как приготовить совершенный бифштекс. ФД хочет чтобы его коровы не увидели эту статью.
ФД взял текст из журнала и создал строку S длиной не более чем 10^6 символов. Из неё он хочет удалить все вхождения подстроки T длиной <= 100 символов неподходящего содержания. Чтобы сделать это, ФД ищет первое вхождение T в S и удаляет его. Затем он повторяет процесс опять, снова удаляя первое вхождение T, продолжая так до тех пор, пока больше не станет вхождений T в S. Заметим, что удаление одного вхождения может создать другое вхождение, которое не существовало раньше.
Пожалуйста, помогите ФД определить конечное содержание строки S после завершения всех удалений.
INPUT FORMAT: (файл censor.in)
Первая строка содержит S. Вторая строка будет содержать T. Длина T не более чем длина S, и все символы S и T - маленькие латинские буквы (a..z).
OUTPUT FORMAT: (файл censor.out)
Строка S после завершения всех удалений. Гарантируется, что S не станет пустой после завершения процесса всех удалений.
SAMPLE INPUT:
whatthemomooofun
moo
SAMPLE OUTPUT:
whatthefun


Наивное решение (делать что написано)
{code:title=p1.cpp|borderStyle=solid}
#include <bits/stdc++.h>
using namespace std;
int main()
{
freopen("censor.in","r",stdin);
freopen("censor.out","w",stdout);
string s,t;
int k,d;
cin >> s >> t;
d=t.length();
k=s.find(t);
while (k>=0)
{s.erase(k,d); k=s.find(t); }
cout << s;
}
{code}
Проходит только первые 2 теста (остальные не проходит по времени).

Для ускорения, рассмотрим построение результирующей строки R, по одному символу за раз.
Если конец R совпадает с T, мы должны удалить его из R.
Поскольку это удаление с конца, оно выполняется за O(1) - resize (изменить длину)

Вот текст соответствующей программы
{code:title=p2.cpp|borderStyle=solid}
#include <bits/stdc++.h>
using namespace std;

int main()
{
freopen("censor.in", "r", stdin);
freopen("censor.out", "w", stdout);

string S, T;
cin >> S >> T;

string R;
for (int i = 0; i < S.size(); i++)
{
R += S[i];
if ((R.size() >= T.size()) &&
(R.substr(R.size() - T.size()) == T))
R.resize(R.size() - T.size());
}
cout << R;
}
{code}
Оно тоже не проходит по времени, начиная с 3-го теста

Теперь основная проблема - эффективно определить совпадает ли конец строки R со строкой T.
Сделаем это хешированием.
{code:title=hash.cpp|borderStyle=solid}
#define HM 1000000007
#define HA 100000007
#define HB 101

/*По заданному хешу h строки S, вычисляем хеш строки S + 'ch' */
int hext(int h, int ch)
{
return (1ll * h * HA + ch + HB) % HM;
}
{code}
Здесь
HA и HB константы полиномиального хеша
HM - модуль, по которому вычисляется хеш
1ll - константа типа long long (длинное целое - до 2^63),
обеспечивающая вычисления в диапазоне long long

Мы должны вычислить хеш от T
{noformat}
int thsh = 0;
for (int i = 0; i < T.size(); i++) {
thsh = hext(thsh, T[i] - 'a');
}
{noformat}
и дополнительно вычислять rolling hash конца R.
Под rolling hash понимается последовательное вычисление хеша строки при добавлении символов к её концу
{noformat}
vector<int> rhsh(1, 0);
vector<int> HAPW(1, 1);
for (int i = 0; i < S.size(); i++) {
/* Добавляем символ к строке R */
R += S[i];

/* вычисляем хеш этой сроки и добавляем в вектор rhsh */
rhsh.push_back(hext(rhsh.back(), S[i] - 'a'));

/* Вычисляем следующую степень HA и добавляем в вектор HAPW */
HAPW.push_back((1ll * HAPW.back() * HA) % HM);


if (R.size() >= T.size()) {
/* Вычисляем хеш |T| последних символов R.
Это делается вычитанием префикса до последних T символов
из хеша общего префикса R (умножая на соответствующую степень HA)
*/
int hsub = (1ll * rhsh[R.size() - T.size()] * HAPW[T.size()]) % HM;
int hsh = (HM + rhsh.back() - hsub) % HM;

/* если конец R и T совпадают, обрезаем конец R
и соответствующие ассоциированные хеш-массивы
*/
if (hsh == thsh && R.substr(R.size() - T.size()) == T) {
R.resize(R.size() - T.size());
rhsh.resize(rhsh.size() - T.size());
HAPW.resize(HAPW.size() - T.size());{noformat}


Полный текст решения
{code:title=all.cpp|borderStyle=solid}
#include <bits/stdc++.h>
using namespace std;

#define HM 1000000007
#define HA 100000007
#define HB 101

int hext(int h, int ch)
{
return (1ll * h * HA + ch + HB) % HM;
}

int main() {
freopen("censor.in", "r", stdin);
freopen("censor.out", "w", stdout);
string S, T;
cin >> S >> T;
int thsh = 0;
for (int i = 0; i < T.size(); i++)
thsh = hext(thsh, T[i] - 'a');
string R;
vector<int> rhsh(1, 0);
vector<int> HAPW(1, 1);
for (int i = 0; i < S.size(); i++)
{
R += S[i];
rhsh.push_back(hext(rhsh.back(), S[i] - 'a'));
HAPW.push_back((1ll * HAPW.back() * HA) % HM);
if (R.size() >= T.size())
{
int hsub = (1ll * rhsh[R.size() - T.size()] * HAPW[T.size()]) % HM;
int hsh = (HM + rhsh.back() - hsub) % HM;
if (hsh == thsh && R.substr(R.size() - T.size()) == T)
{
R.resize(R.size() - T.size());
rhsh.resize(rhsh.size() - T.size());
HAPW.resize(HAPW.size() - T.size());
}
}
}
cout << R << endl;
return 0;
}{code}