S>"До хрена и больше" — сколько именно?
S>Какие длины у этих сигнатур — все одинаковые/сильно разные/более-менее похожие?
S>Что вы тут называете N? Количество сигнатур или длину бинарной последовательности, в которой вы ищете данные?
S>Что у вас чаще меняется — строка, в которой ищут, или набор сигнатур?
Приблизительный порядок количества сигнатур — десятки миллионов, с линейным ростом на сотни тысяч в месяц, регулярность пополнения — единицы раз в день. Длины, навскидку, от 6 до 64 байт. На остальные вопросы ответа дать не готов, т.к. всё это пока жуткая экспериментальщина, далекая от реального использования, и сценарии использования могут кардинально поменяться в процессе.

S>В общем, предварительно напрашивается Ахо-Корасик. Он спроектирован ровно для вашей задачи.
Спасибо, да, один из очевидных вариантов. Посмотрю. Однако, бросаться на амбразуру и сразу строить единый граф поиска с таким количеством сигнатур все же, наверное, перебор.
Ради прикола, конечно, попробую Ragel, транслирующий БНФ-нотацию в C-код: он может быть даже всё это хозяйство прожуёт скопом, но в прод такое пускать — жесть Предсказуемость поведения по мере роста корпуса сигнатур под вопросом.

Поэтому тут напрашивается некий упрощенный пре-фильтр. Например, триграммы. Правильной нарезкой на оные, к слову, тривиально реализуется даже индексируемость под поиск по регуляркам, как это было сделано в Google Code Search, хоть это и несколько другая задача:
http://swtch.com/~rsc/regexp/regexp4.html
https://github.com/google/codesearch/

Да и на случай нетекстовых символов оно вполне экстраполируется, т.к. не влечёт никаких допущений о природе документов и сигнатур.

То есть можно попробовать такую двухходовочку: сначала с помощью триграмм получаем сигнатуры-кандидаты, которые "скорее всего" содержатся во входной последовательности.
Затем алгоритмом Ахо-Корасик ищем по этой последовательности за один проход сокращенным множеством сигнатур-кандидатов.