Самый быстрый алгоритм поиска строки для фиксированного текста и большого количества подстрок

Question

Я пытаюсь найти алгоритм для поиска двоичных строк фиксированного размера (64 бита) в большом двоичном буфере (100 МБ). Буфер всегда один и тот же, и у меня есть много и много строк для поиска (возможно, 2 ^ 500). Я должен найти все вхождения любой данной строки, а не только первую.

Какой алгоритм я могу выбрать? Возможно тот, который извлекает выгоду из постоянного буфера, в котором я ищу.

Ссылки на исходный код C для такого алгоритма приветствуются.

Answer 1

Предполагая, что ваша строка выровнена по 8 битам, из буфера 100 МБ вы получите 100 миллионов различных строк, которые можно поместить в хеш-таблицу размером примерно 800 МБ с постоянным (O (1)) временем доступа.

Это позволит вам выполнить поиск максимально быстро, поскольку, получив 8-байтовую строку, вы сразу узнаете, где эта строка была замечена в вашем буфере.