@N
Думаю, если пойду в телеком, то и алгебру с байесом найду куда втулить
Size: a a a
2021 May 16
YB
в общем случае O(n) каждый раз))
YB
один массив полиномиальных хешей эт O(n) согласен
CD
так вопрос - если у тебя две строки S1 и S2 и ты знаешь poly(S1) и poly(S2), можешь посчитать poly(S1+S2)?
YB
ну в этом случае будет O(1)
YB
не спорю
CD
как только это О(1), хеш подстроки не может быть дольше log-а
CD
любой ассоциативный фолд считается за лог :)
YB
я думал в любом случае динамическим программированием считать массив хешей, тогда O(n)
YB
всё равно же травёрсить по строке для проверки подстрок на палиндром
CD
ну O(n) предпросчёт + О(1) на запрос подстроки
CD
и N * log N запросов "что там вот по этому отрезку"
V
Да это хуйня, просто бабки на базаре
V
Разумеется, никто нихуя делать не будет
V
Ну разве что террористы из Хизбаллы подключатся
CD
7 лет такого не было и вот опять?
PO
Шо? Костя не писал полиномиальные хэши?
YB
Скандалы интриги расследования
PO
Лучше не пиши такого, ты оскорбляешь деда)
YB
Не, в треде он не писал, что именно полиномиальное хеширование юзать будет