Тема: STL
http://contests.snarknews.info/files/sn … s/day3.pdf
как можно решить эту задачу не используя бор. А именно есть ли в STL какая-та библиотека что-ли?
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » STL
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
http://contests.snarknews.info/files/sn … s/day3.pdf
как можно решить эту задачу не используя бор. А именно есть ли в STL какая-та библиотека что-ли?
можно стандартно хешами.
А как можно хранить хэши?
надо вроде бы хранить массив power, где будут находиться степени какого-то р, но при длине,скажем, N<=100000, невозможно хранить такое большое число.
В целом где можно найти статью про хэши? в этом сайте дана статья про хэши с короткой длины
В этом то и фишка хеша что нам не надо его полностью вычислять достаточно обрезать по int/long long или по модулю большого числа. Вероятность ошибок остается мизерной.
Алгоритм http://e-maxx.ru/algo/rabin_karp продолжает работать даже при строках в N = 100000.
Еще раз перечитай http://e-maxx.ru/algo/string_hashes.
Можете реализацию Рабина - Карпа отправить с модулем и т.д. Спасибо...
На практике лучше просто обрезать по int/long long (что по сути тот же модуль) так будет быстрее и больший диапозон хешей.
a esli delat' tak:
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
int main()
{
map <long long, int> A;
int n , m;
scanf("%d%d", &n, &m);
for (int i=0; i<n; i++)
{
string s;
cin>>s;
long long hash = 0;
for (int j=0; j<s.size(); j++)
{
hash = hash * 31 + (s[j]-'a'+1);
A[hash]++;
}
}
for (int i=0; i<m; i++)
{
string s;
cin>>s;
long long hash = 0;
for (int j=0; j<s.size(); j++) hash = hash * 31 + (s[j]-'a'+1);
cout<<A[hash]<<"\n";
}
return 0;
}
U menya TL 72test
Можно избавиться от cin/cout, если и так не пройдет - заменить map на отсортированный массив или хешмап.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » STL