Просмотр источника
Вместо 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} |