@N
Строковые алгоритмы вспоминаешь только.. когда работаешь со строками. Делаешь текстовый редактор с фичами
Size: a a a
2021 May 16
YB
O(n log n) то есть и как хэшами O(n) тоже наверн не видел я кек
PO
Не на олимпиадках палиндромы искал только один раз в жизни и там потребовались полиномиальные хэши + до
YB
но хэшами наверн просто окно двигаешь и реверснутую строку хэшируешь))
YB
но хэшами O(n) не достичь всё таки
YB
это ж тоже O(n^2)
CD
бинпоиском от текущей позиции - при одинаковом центре подстроки палиндрома палиндром
PO
nlogn
YB
хэш от всей строки O(n) же
YB
и ты окно ещё двигаешь
CD
хэш любой подстроки О(1)
YB
YB
ну почти
PO
Ну строковые алгоритмы не обязательно при работе со строками нужны жи)
PO
Мне приходилось ловить наборы дискретных точек
PO
Чтобы багу отловить
@N
Мне вот в жизни как-то больше алгоритмы на графах и геом всякий пригодились
PO
Ну это тоже
CD
можешь посчитать полиномиальный хеш конкатенации, зная хеши частей?
YB
ты не писал полиномиальное хеширование))