hash_set, hash_map, хеш-функция - DL Руководство пользователя

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

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

А вместо hash_map - unordered_map

Хеш-таблица

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;

Хеш-функция

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

Наивное решение (делать что написано)

p1.cpp

#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;
}

Проходит только первые 2 теста (остальные не проходит по времени).

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

Вот текст соответствующей программы

p2.cpp

#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;
}

Оно тоже не проходит по времени, начиная с 3-го теста

Теперь основная проблема - эффективно определить совпадает ли конец строки R со строкой T.
Сделаем это хешированием.

hash.cpp

#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;
  }

Здесь
HA и HB константы полиномиального хеша
HM - модуль, по которому вычисляется хеш
1ll - константа типа long long (длинное целое - до 2^63),
обеспечивающая вычисления в диапазоне long long

Мы должны вычислить хеш от T

  int thsh = 0;
  for (int i = 0; i < T.size(); i++) {
    thsh = hext(thsh, T[i] - 'a');
  }

и дополнительно вычислять rolling hash конца R.
Под rolling hash понимается последовательное вычисление хеша строки при добавлении символов к её концу

  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());

Полный текст решения

all.cpp

#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;
}