Хэширование

14 лет назад, # |

Ну по крайней мере в первой задаче за O(n log²n) можно совсем просто: бинпоиском фиксируем длину ответа и за O(n log n) хэшами проверяем, если две совпадающие строки.

Во второй, судя по всему, работает та же самая идея. Только хэш, наверное, нужно брать полиномиальный от двух переменных.

Но и здесь, и там хэши используются именно что для быстрого сравнения строк.

→ Ответить

Krot	14 лет назад, # ^ \| 0 По поводу 2 пункта: Пробегаемся по всей, например первой строке, вычисляя хэш функцию на подстроке и за O( log(sqr(n)) ) ищем это значение среди O(n*n) хэшей второй строки. Я правильно понял? → Ответить

Krot	14 лет назад, # ^ \| 0 Только вот наверное надо будет сортировать второй список хэшей, но их там O(n*n). В обшем, можно поподробнее 2 пункт? → Ответить

14 лет назад, # ^ |

Речь идёт о первой задаче? При фиксированной длине строки у нас O(n) хэшей, каждый из которых можно вычислить за O(1), если сделать очевидную предобработку.

→ Ответить

Krot	14 лет назад, # ^ \| ← Rev. 3 → 0 Да, речь идет о первой задаче → Ответить

Krot	14 лет назад, # ^ \| 0 Непонятно как "за O(n log n) хэшами проверяем, если две совпадающие строки" → Ответить

Krot	14 лет назад, # ^ \| 0 Если мы вычислили хэш, как его найти во второй строке? → Ответить

Krot	14 лет назад, # ^ \| +1 А, все понял: просто сольем две строки и все → Ответить

Krot	14 лет назад, # ^ \| +1 Складываем эти две строчки, потом бинпоиском по длине считаем хэши для строк нужной нам длины, сортируем этот список хэшей и проверяем, нет ли двух одинаковых? → Ответить

Krot	14 лет назад, # ^ \| 0 нет, извиняюсь неверно) → Ответить

14 лет назад, # ^ |

Ну, это не правильно: ты можешь найти две одинаковые подстроки в одной и той же строке.

→ Ответить

Krot	14 лет назад, # ^ \| 0 Да, я поторопился, поэтому и написал "неверно". → Ответить

http://acm.timus.ru/problem.aspx?space=1&num=1713

14 лет назад, # ^ |

Смотри, фиксируем длину строки k. Выписываем O(n) хэшей подстрок длины k в первой строке, и столько же во второй. Теперь у нас есть два набора из n чисел, надо надо найти пару одинаковых. Это можно сделать ровно 100500 способами за O(n log n), например отсортировав оба набора и пробежавшись по ним двумя указателями.

→ Ответить

Krot	14 лет назад, # ^ \| 0 Да, да, я все понял, огромное спасибо!). Не подскажите каких-нибудь интересных задач или ключевых идей на эту тему? → Ответить

maksay

14 лет назад, # ^ |

Могу посоветовать

Решается хешами и совсем не просто как по мне - я долго мучался на грани ТЛ/МЛ/ВА:)

→ Ответить

hydrastuff

14 лет назад, # ^ |

ключевым шагом для АС у меня было замена типа хеша с long long на int =)

→ Ответить

Urbanowicz

14 лет назад, # ^ |

Это пример задачи, которую хешами лучше не решать. Ее лучше бором.

→ Ответить

opensource

14 лет назад, # ^ |

← Rev. 2 →

Не могли бы Вы посоветовать что-нибудь, чтобы решить эту задачу? Я очень долго мучился, так и не смог пройти ТЛ 3 тест.

Мое решение: для каждой строки делаю бинпоиск по длине К. Для каждой длины К - запускаю функцию, где заношу все хеши длины К других строк в таблицу. После перебираю все подстроки текущей строки длины К.

Естественно, таблицу, по выходу из этой функции, очищаю.

Надеюсь, я понятно объяснил. 64битный тип на 32 уже поменял.

Thx in advance

→ Ответить

14 лет назад, # ^ |

Скорее ошибка в реализации, т.к. первый большой тест - это девятый. Может быть вы ошиблись при выполнении бинпосика.

→ Ответить

opensource

14 лет назад, # ^ |

Спасибо за ответ. Но, по-моему, зря Вы сомневаетесь в моем бинпоиске.

Основная идея является правильной?

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

[увеличваем_строку_чтобы_текст_нормально_читался_а_не_по_слову_в_строке]

бинпоиск не нужен. делаем цикл по длине от 1 до 100
X кидаем все подстроки длины k всех строк в хеш таблицу
X перебираем строки для которых еще нет ответа
XX выкидываем из хеш таблицы все подстроки длины k нашей фиксированной строки
XXX смотрим в хеше есть то что нас интересует или нет
XX добавляем в хеш таблицу все подстроки длины k нашей фиксированной строки

→ Ответить

opensource

14 лет назад, # ^ |

Спасибо_за_развернутый_и_полный_ответ. Буду_пробовать. Оказывается, моя идея была в корне не правильной.

→ Ответить

14 лет назад, # ^ |

_______________Не_хочу_узкий_текст_____________

А я решил бинпоиском по длине. Далее перебираем все хеши строк длины k. Сортируем и находим есть ли совпадающие хеши.

Асимптотика nlog^2n (logn бинпоиск, nlogn - проверка).

Так что такое решение допустимо :)

→ Ответить

14 лет назад, # ^ |

не понял твоего объяснения. сомневаюсь что у тебя оценка времени лучше.

→ Ответить

14 лет назад, # ^ |

Ну не знаю я сегодня сдал её этим способом, оценка времени 0.593 сек.

→ Ответить

14 лет назад, # ^ |

это же разные задачи. мы говорим об этой. её решение кинь в everfall/paste посмотрим

→ Ответить

14 лет назад, # ^ |

Поленился посмотреть на главный коммент, извините пожалуйста ;)

→ Ответить

Jokser

14 лет назад, # ^ |

http://acm.timus.ru/problem.aspx?space=1&num=1414
http://acm.timus.ru/problem.aspx?space=1&num=1542
Хэш+Сет я делал.

Попробуй еще просто набор строк отсортировать по алфавиту за N*LogN*LogM, N - кол-во строк, M - длина строк. Бинарный поиск по совпадающему хэшу.

Еще хэшированием найти мининимальный циклический сдвиг. Тоже бинарный поиск по совпадающему хэшу.

Да и вообще много задач разных.

→ Ответить

Zhandos

14 лет назад, # ^ |

← Rev. 2 →

Как ты 1542 задачу делал ? Можешь плз по подробнее рассказать алгоритм с хэшами?

→ Ответить

_Vadim_

13 лет назад, # ^ |

Пусть у Вас есть набор хешей длины k первой строки и второй строки. Вы же не можете просто в лоб сравнить их, т.к. эти хеши умножены на разные коофициенты (т.е. hash_of_string1 = s1[i]*p^i + s1[i+1*p^(i+1) + s1[i+k-1]*p^(i+k-1)

hash_of_string2 = s2[j]*p^j + s2[j+1]*p^(j+1) + s2[j+k-1]*p^(j+k-1)

Т.к. i != j и строки взяты по какому-то модулю, просто их сравнить нельзя.) Я в таких случаях домнажаю первый хеш на p^o1, а второй - на p^o2 так чтобы i + o1 = j + o2. Существует ли иное решение этой проблемы?

→ Ответить

dalex

13 лет назад, # ^ |

Не существует

→ Ответить

permin

13 лет назад, # ^ |

а за O(n) нельзя? :)

→ Ответить

VladGanzha

12 лет назад, # ^ |

Получаем порядка n хэшей для каждой длины подстроки,поэтому сложность, по-моему, будет n*(n log n).

→ Ответить

Jokser

14 лет назад, # ^ |

Вот помнится решал эту задачу хэшами + бин. поиск. Да только они так и не прошли, сколько не запихивал. Видимо, где-то коллизии были. Использовал хэширование, которое дано в e-maxx.

→ Ответить

Salat

14 лет назад, # ^ |

>Во второй, судя по всему, работает та же самая идея. Только хэш, наверное, нужно брать полиномиальный от двух переменных.

а как брать хэш от произвольного квадрата в матрице?

например (семпл из задачи 1448):

5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl

Допустим нужно вязть хэш от квадрата (0,0) (3,3)

сначала берем хэши от строк (от строк понятно как брать), а потом полученные хэши как-то сложить? Если да, то как?

→ Ответить

Ripatti

14 лет назад, # ^ |

пусть у нас есть 2 простых числа - p и q
тогда букве в прямоугольнике a[i,j] сопоставим величину a[i,j]*p^i*q^j (i, j, конечно же, считаются от левой и верхней границ выбранного прямоугольника). хэшом будет сумма этих величин по всему прямоугольнику.
как после предпросчета всей таблицы за О(1) находить хэш для любого прямоугольника - догадаться несложно...

→ Ответить

Salat

14 лет назад, # ^ |

Спасибо понял, оказывается вообще не в ту сторону думал!)

→ Ответить

Prestige

13 лет назад, # ^ |

← Rev. 3 →

Сорри, может я тупой!Но непонятно по задаче 1517.Что значит фиксируем длину ответа?

→ Ответить

_Vadim_

13 лет назад, # ^ |

Ты перебираешь бин. поиском длину ответа (длину строки, которая будет являться ответом на задачу).
int l = 0, r = s.length();

while (r > l)

{

int m = (l + r)/2;

if (f (m)) l = m; else r = m-1;

}

if (f(l)) cout << l; else cout << "-1";

f(len) - это функция, которая проверяет может ли строка длины len быть ответом.

→ Ответить

Krot	14 лет назад, # \| 0 Раз уж пошла речь о хэштровании: какие наиболее хорошии фукнции существуют, кроме той, которая описана на сайте e-maxx? → Ответить

Light_Yagami

14 лет назад, # |

-7

zaminusuyte menya plz!

→ Ответить

freopen

14 лет назад, # ^ |

Тем, кто из вредности плюсует такие комменты, я бы посоветовал сводить рейтинг автора к 0. Это куда обиднее :)

→ Ответить

I-juice

14 лет назад, # |

Например, вот эта задача очень просто решается хэшами: http://mirror.codeforces.com/problemset/problem/7/D

→ Ответить

14 лет назад, # |

Однажды мне один крутой асмер сказал, что он не знает ничего про строки кроме хешей и он сдает 90 % задач ими. Потом Саша Прудаев из Тюмени так вообще на всех контестах сдавал задачи на строки в первый час, которые другие сдавали в конце контеста и тоже хешами) Я пишу хеш почти всегда, когда вижу задачу на строки - потому что а) их написать быстро б) не так сложно придуать в) если не пройдет (вдруг), то будет прога которая более менее затестит нормальное решение.
примеры задач некоторые
1) http://acm.timus.ru/problem.aspx?space=1&num=1486
2) http://acm.timus.ru/problem.aspx?space=1&num=1590 - вообще подходит для любого алгоритма
3) http://acm.timus.ru/problem.aspx?space=1&num=1425 - не на строки, но я помню, сдавал хешами
Тут вообще много задач кинули, но если нужно еще задач интересных, пиши в личку)

→ Ответить

Ripatti

14 лет назад, # |

Первую за O(nlogn) решать так:
Бинпоиск по длине ответа. Пусть длина k. Тогда вычисляем O(n) полиномиальных хэшей подстрок длины k первой строки за время O(n) и складываем их в хэш-таблицу. Потом проходимся по подстрокам длины k второй строки и смотрим - лежить ли в хэш-таблице нужный хэш. После проверки для k хэш-таблицу аккуратно очищаем.

Вторую задачу абсолютно аналогичным образом можно решить за O(N^2logN).

→ Ответить

http://skidanovalex.ru/slides/phashes.pptx

14 лет назад, # |

Вот может будет полезно, я как раз недавно читал лекцию по полиномиальным хешам:

→ Ответить

Krot	14 лет назад, # ^ \| 0 Спасибо, интересно, только непонятно: там что-то недописано или это у меня у половины страниц только заголовки? → Ответить

http://skidanovalex.ru/slides/phashes.ppt

14 лет назад, # ^ |

Нет, все слайды там. Может из-за того, что сохранял в 2010 powerpnt.

Попробуй

→ Ответить

14 лет назад, # ^ |

А где читал?

→ Ответить

14 лет назад, # ^ |

Здесь нашим ребятам русскоговорящим. В неформальной обстановке :о)

→ Ответить

Krot	14 лет назад, # ^ \| 0 Все, теперь все видно, огромное спасибо! → Ответить

Kh.Madi

14 лет назад, # ^ |

Спасибо за хорошую презентацию!

Я не очень понял один момент.

Вы написали:

v(A,i,j) = x1*v(A,i,j-1)+A_i,j-1

h(A,i,j) = x2*h(A,i-1,j)+v(A,i-1,j).

Какое значение будет у h(A,0,j) ?

→ Ответить

Krot	14 лет назад, # \| 0 Еще вопрос очень важный: какие именно хэши использовать? Я про одномернуй задачу(1517), и про двумерную(1486) → Ответить

14 лет назад, # ^ |

Я и там и там писал полиномиальный

→ Ответить

udalov

14 лет назад, # ^ |

А какие ещё бывают О_о? Вернее, для каких целей может пригодиться какой-либо неполиномиальный хэш?

→ Ответить

14 лет назад, # ^ |

Разные бывают методы хеширования) Но для строк я по-моему ни разу не писал не полиномиальный хеш, однако видел код, где был другой метод.
Я просто не понял вопрос "какие именно хэши использовать?" - единственное, что пришло на ум - полиномиальные)

→ Ответить

http://en.wikipedia.org/wiki/Hash_map_(C%2B%2B)

14 лет назад, # |

Ответ на новый вопрос: нет, hash_map есть не везде. Например, везде где в качестве компилятора стоит студия, его нет.

Встречный вопрос: зачем тебе hash_map? :о) Если мне не изменяет память (поправьте меня, если я не прав), там медленная реализация, и если обычный map не проходит, hash_map не панацея -- все равно надо писать хеш табличку ручками.

→ Ответить

Arkadiy

14 лет назад, # ^ |

← Rev. 2 →

Разве нет в студии?

#include <hash_set>
#include <hash_map>

using namespace std;
using namespace stdext;

int main () {
hash_set <int> w;
hash_map <int, int> w2;

return 0;

}

Всё замечательно компилируется.

upd: про hash_map не знаю, но hash_set работает медленее примерно в два раза в сравнении с ручной реализацией (как то давно тестировал немного).

→ Ответить

freopen

14 лет назад, # ^ |

Ну, кажется она ругается warningами на него. Когда нибудь они его выкинут (когда допилят аналогичную фичу в C++0x)

→ Ответить

Krot	14 лет назад, # \| 0 Я просто увидел несколько решений с использованием hash_map'a, поэтому и спросил не рискуют ли люди на соревновании, когда так делают) → Ответить

Urbanowicz

14 лет назад, # ^ |

hash_map, скорее всего, имеется везде, но разные компиляторы хранят его заголовочные файлы в разных местах. Кроме того, еще namespace по-разному называются.

→ Ответить

mastersobg

14 лет назад, # |

HashSet и HashMap используются часто. Но это Java...

→ Ответить

14 лет назад, # |

← Rev. 3 →

Написал решение по второй задачи за O(n ^ 2 * log ^ 2 (n))

Но оно таймлимитится(((

Вот решение http://pastebin.com/rHtX5KYe

подскажите плз что не так.

→ Ответить

14 лет назад, # ^ |

← Rev. 4 →

что еще тут можно с оптимизировать?

Если использую map то решение ловит мемори лимит, set не получается использовать проблема

потом возникает в поиске.

Кстати как использовать set так чтобы можно было найти элемент по одному только хэшу

то есть

set<pair<long long,pair<int,int> > > set;

first это хэш и second это координаты области.

вот как мне проверить есть ли в set хэш.

set.find(hash); - так не катит требует структуру pair<long long,pair<int,int> >

→ Ответить

Vasya.V

14 лет назад, # ^ |

1) Могут сильно тормозить new / delete

2) Думаю, что асимптотика O(n^2 * log^2 (n)) недостаточно хороша

Мое решение O(n^2 * log(n)) с самописной hash_map без динамической памяти заходит за 0.3 с, а лишний log(n) раз в 8 замедляет решение -> TL

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

хм я даже не знаю где log(n) может быть лишний,

1-ый тот что по длине стороны квадрата идет.

2-ой тот что проверяет наличие хэша,.

попробую как нибудь избавить от new и delete

→ Ответить

Vasya.V

14 лет назад, # ^ |

log(n) от бинпоиска

Вставка/поиск в дереве - log(n)

Вставка/поиск в hash_map - O(1)

Кстати, дерево у тебя без балансировки. 99%, конечно, что при хранении хешей его высота будет расти как O(log(n)), но все же

→ Ответить

14 лет назад, # ^ |

>Вставка/поиск в hash_map - O(1),

круто, даже не знал, спасибо.

→ Ответить

NikitaD

14 лет назад, # ^ |

Насчет того, как использовать set.

можно завести структурку, типа:

struct elem {
long long hash;

pair <int, int> c;
elem (long long _hash): hash(_hash) {}

};

и перегрузить оператор <:

bool operator < (const elem & a, const elem & b)
{
return a.hash < b.hash;
}

Тогда, по-идее, будет нормально работать set.find(elem(hash));

→ Ответить

14 лет назад, # |

А какое лучше использовать простое число для вычисления хеша?

(Слышал что при использовании маленьких латинских букв хватит 31)

→ Ответить

_jte_

14 лет назад, # ^ |

← Rev. 2 →

Ну, обычно стараются следовать 2 параметрам:

1) ~~модуль~~ p - просто число

2) значение ~~модуля~~ p близко размеру алфавита, желательно чуть больше. К примеру, для строчных английских букв отлично подходит что-то типа 29, 31.

→ Ответить

14 лет назад, # ^ |

Я имел ввиду другое

h(S) = S[0] * P^N + S[1] * P^(N-1)+ S[2] * P^(N-2)+ S[3] * P^(N-3)+ ... + S[N]

Я подразумевал простое число P, которое вы возводим в степень, а не модуль.

→ Ответить

_jte_

14 лет назад, # ^ |

это я плохо написал, я именно это просто число и имел в виду под модулем, сорри за непонятность.

в качестве взятия по модулю мы обычно же ничего не делаем, беря хеш по 2 ^ (длина типа в битах)

→ Ответить

14 лет назад, # ^ |

Спасибо :)

→ Ответить

14 лет назад, # |

← Rev. 2 →

→ Ответить