ZZ>Дано: антивирусоподобная система, хранящая в себе до хрена и больше бинарных сигнатур.
ZZ>Требуется: искать сигнатуры по совпадению с бинарной подпоследовательностью за асимптотическое время меньшее, чем O(N).

Помнится, в прошлый раз я просто строил из всех сигнатур один большой конечный автомат (препроцессинг). Но это работало на отдельном appliance, где памяти было много. В случае работы на клиентских устройствах столько памяти может и не быть.