Здравствуйте, zx zpectrum, Вы писали:

ZZ>Дано: антивирусоподобная система, хранящая в себе до хрена и больше бинарных сигнатур.
"До хрена и больше" — сколько именно? Какие длины у этих сигнатур — все одинаковые/сильно разные/более-менее похожие?
Влезут ли все эти сигнатуры в RAM?
ZZ>Требуется: искать сигнатуры по совпадению с бинарной подпоследовательностью за асимптотическое время меньшее, чем O(N).
Что вы тут называете N? Количество сигнатур или длину бинарной последовательности, в которой вы ищете данные?

Что у вас чаще меняется — строка, в которой ищут, или набор сигнатур?
Ну, то есть что нужно "проиндексировать" заранее: набор сигнатур, через который нужно прогнать M документов, или набор документов, через которые потом будете прогонять различные сигнатуры?

В общем, предварительно напрашивается Ахо-Корасик. Он спроектирован ровно для вашей задачи.

ZZ>PS. Внутренний голос мне подсказывает, что с этим, скорее всего, на ура справится Постгрес, достаточно лишь правильно его приготовить. Например, индексировать N-грамы, а не корни слов. Если кто-либо из присутствующих занимался чем-то подобным, буду очень благодарен ссылочкам на книги и статьи.
АФАИК, коробочной версии для постгреса нету. К нему можно прикрутить того же Ахо-Корасика, но стоит ли овчинка выделки?