Тема: Timus 1590 hash
Как можно решить http://acm.timus.ru/problem.aspx?space=1&num=1590 при помощи хэша ? Алгоритм поиска кол-ва различных подстрок http://e-maxx.ru/algo/string_hashes дает ТЛЕ.
Re: Timus 1590 hash
Можно решать, например, так (описано в самом низу страницы).
Re: Timus 1590 hash
А разве перебирать все подстроки и кидать в хеш-таблицу не успеваем по времени?
Re: Timus 1590 hash
Нет, там ТЛЕ тест 3. А у кого-нибудь она прошла хешами? Просто говорят что можно 80% задач на строки решать хешами. Я и хочу теперь все хэшами делать) Другим способом я уже решил.
Re: Timus 1590 hash
А покажи кусок кода в котором ты вычисляешь все хеши.
Подозреваю что там у тебя O(N^3)
Re: Timus 1590 hash
const unsigned long long pr = 97;//97 1039
unsigned long long h[6000], h1, _pow[6000];
char s[5000];
int n, res = 0;
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","rt",stdin);
freopen("output.txt","wt",stdout);
#endif
scanf("%s", &s); n = strlen(s);
h[0] = 0; _pow[0] = 1;
for (int i = 1; i <= n; i++)
h[i] = h[i - 1] * pr + s[i - 1], _pow[i] = _pow[i - 1] * pr;
for (int k = 1; k <= n; k++)
{
vector<unsigned long long> all;
for (int i = 0; i + k <= n; i++)
{
h1 = h[i + k] - h[i] * _pow[k];
all.pb(h1);
}
sort(all.begin(), all.end());
all.erase (unique (all.begin(), all.end()), all.end());
res += all.sz;
}
printf("%d\n", res);
return 0;
}Re: Timus 1590 hash
Еще правда пробовал вместо sort использовать и map, и set. Все равно ТЛЕ
8 2011-04-08 21:41:54 Отредактировано coder.ua (2011-04-08 21:59:26)
Re: Timus 1590 hash
Меня тоже заинтересовала эта задача. Я написал на неё хеш, но он на макс тесте работает 3 секунды, хотя на одну ячейку у меня не больше чем 36 коллизий. Можно конечно пошаманить, но боюсь по памяти не пройдёт.
Странно, что сетом не проходит...
Re: Timus 1590 hash
Ну так это уже не квадрат, а N^2logN, причем операции с вектором лонг лонгов. Многовато.
Re: Timus 1590 hash
А ты можешь решить хешами?
Re: Timus 1590 hash
На такой длине можно попробовать интовый хеш - поподбирать нужную базу хеша придётся тогда, ибо коллизии на интовом хеше - не редкость. Но зато инт гораздо быстрее, раз уж так хочется именно хешом решать эту задачу.
Re: Timus 1590 hash
Ради интереса только что сдал с лонг лонговским хешом и ручным хешсетом.
Re: Timus 1590 hash
На такой длине можно попробовать интовый хеш - поподбирать нужную базу хеша придётся тогда, ибо коллизии на интовом хеше - не редкость. Но зато инт гораздо быстрее, раз уж так хочется именно хешом решать эту задачу.
Я так и делаю. Я вычисляю один хеш по модулю 10^6, а второй по 2^32, по первому "вяжу" в связный список, а по второму сравниваю. Вероятность того, что разные строки дадут одинаковые хеши как по первому хешу,так и по второму очень мала. На рандомном тесте работает 3 секунды, хотя максимальная глубина списка - 36,как я уже говорил.
Ради интереса только что сдал с лонг лонговским хешом и ручным хешсетом.
Скажи пожалуйста как ты писал свой ручной хешсет, если не секрет.
14 2011-04-08 23:27:43 Отредактировано KADR (2011-04-08 23:28:04)
Re: Timus 1590 hash
Для этой задачи написал вот такой простенький хешсет, который добавляет элемент если такого в нем не было и возвращает 1 или 0 в зависимости от того, был ли добавлен элемент.
int last[MOD],nx[5001];
unsigned ll key[5001];
inline bool add(unsigned ll h)
{
for (int w=last[h%MOD];w>=0;w=nx[w])
{
if (key[w]==h) return 0;
}
int o=h%MOD;
key[k]=h;
nx[k]=last[o];
last[o]=k++;
return 1;
}Re: Timus 1590 hash
Добавление у меня такое же, но я кажется понял в чём ошибка у меня: ты наверное перебираешь все подстроки по длине сначала, а потом очищаешь список. Я же всё кидал в один список...:/
Большое спасибо за помощь!
Re: Timus 1590 hash
На этом форуме один добрый юзер выложил архив 2010 ЛКШ
http://e-maxx.ru/forum/viewtopic.php?id=267
там в один из дней эта задача есть. Правда там ограничения написаны 2000. но формулировка идентичная. И название идентичное.
В архиве в папке B есть задача bacon.7z там есть тесты, и миникаменты от жури.
В них немногозначно написано
"для каждой подстроки подсчитать ее хеш-функцию".
Значит копаем мы в правильном направлении 
Кстати, где можно достать архивы ЛКШ других годов?
17 2011-04-08 23:37:30 Отредактировано KADR (2011-04-08 23:38:12)
Re: Timus 1590 hash
coder.ua пишет:
Добавление у меня такое же, но я кажется понял в чём ошибка у меня: ты наверное перебираешь все подстроки по длине сначала, а потом очищаешь список. Я же всё кидал в один список...:/
Большое спасибо за помощь!
Да, я после проверки очередной длины очищаю хешсет.
Re: Timus 1590 hash
Всем спасибо. KADR спасибо за помощь. Сдал на АС 0.921 
Re: Timus 1590 hash
Кстати, есть ещё такое интересное решение:
Строим бор по суффиксам исходной строки. Теперь что представляет из себя вершина бора? - префикс одного из суффиксов. Все префиксы всех суффиксов - все подстроки. Очевидно, что одинаковых префиксов в боре не будет. Теперь мы доказали, что количество вершин в таком боре - количество разных подстрок.
Re: Timus 1590 hash
Только, наверно, в этой задаче бор будет сложно в память запихать? Как-никак, миллионов 5-10 вершин в нём будет.
Если говорить о не-хешовых решениях, то видимо проще всего будет с помощью префикс или z-функции за квадрат: рассматривая символы строки по одному слева направо и поддерживая текущее число различных подстрок.
Re: Timus 1590 hash
Да в память не влезет 100%, но идея изящнее хешей
А можно поподробнее с п-функцией идею рассказать?
Re: Timus 1590 hash
Кратко идея решения такая: начнём с пустой строки, и будем дописывать к ней по одному символу в начало, и поддерживать текущее число различных подстрок.
Изначально, когда буква одна, - подстрока одна.
Теперь как пересчитывать это количество при добавлении одного символа в начало строки? Понятно, что все старые подстроки останутся, а добавятся подстроки, начинающиеся с добавленного символа, и не встречающиеся больше нигде в текущей строке. Т.е. нам надо научиться считать для текущей строки, сколько есть у неё префиксов, не встречающихся более внутри неё. Это делается с помощью z- или префикс-функции.
Re: Timus 1590 hash
А, ну кстати по решению с бором - не всё так плохо, можно строить сжатый бор - за квадрат его строить не так уж и сложно, а точнее, почти не сложнее обычного бора. А размер сжатого бора (aka суффиксного дерева), как известно, линеен.
Re: Timus 1590 hash
Спасибо!
Касательно суффиксного дерва, насколько я знаю, там не далеко уже и до дерева Укконена.
Re: Timus 1590 hash
e-maxx пишет:
А, ну кстати по решению с бором - не всё так плохо, можно строить сжатый бор - за квадрат его строить не так уж и сложно
а смысл тогда, если хешами тоже за квадрат решаем с меньшим напрягом