Если часто искать нужно будет, то префиксное дерево.

Каким образом префиксное дерево здесь поможет? Оно хорошо для линейного поиска подстрок, но каким боком его здесь прикрутить не понимаю.

http://lmgtfy.com/?q=Perfect hashing

Оно хорошо для линейного поиска подстрок

Эммм ну да ... Любая строка является подстрокой самой себя.

Если хеши совпали, то для достоверности нужно проверять посимвольно.

Если хеши совпали, до кучи сравнить длины строк.

Я не считал, но есть подозрение что на нескольких десятках тысячах строк возможность совпадения хешей, космически мала.

Вот в гите сколько коммитов в дереве? И никто не очкует по-поводу совпадения хешей sha1.

Пишешь код для атомного реактора или как?

В общем, париться по-этому поводу следует после вычисления вероятности совпадения хеша, и осознания неудовлетворённости цифрой.

Все строки можно препроцессить заранее.
Если хеши совпали, то для достоверности нужно проверять посимвольно.

Ты на этапе препроцессинга должен подобрать такую хэш-функцию, которая дает маленькое число коллизий. Удобное семейство хэш-функций, в котором можно искать подходящую, это подсоленная md5: https://ru.wikipedia.org/wiki/Соль_(криптография) . Нужно генерировать случайную соль до тех пор, пока получившаяся из этой соли хэш-функция не даст хэш-таблицу с маленьким числом коллизий.

PS разумеется, вместо md5 можно взять любую другую относительно криптостойкую хэш-функцию

PPS ну и разумеется, чтобы говорить о гарантированном совпадении образца с одной из заготовленных строк, необходимо выполнить посимвольное сравнение

Никакой драмы в этом посимвольном сравнении нет: чтобы вычислить хэш-функцию от образца, ты и так уже один раз этот образец посимвольно просмотрел. Просмотришь и во второй раз, ничего страшного.

префиксное дерево

суффиксное же

урлы?

У деревьев проблемы с локальностью данных, это ставит крест на быстродействии.

суффиксное

Ой, мне показалось что ТС нужны подстроки. Отбой суффиксным деревьям

Использовать sha1 в данном случае жирно, он медленный и размер хеша большой. Если же взять к примеру 64 бита, то коллизии будут вполне реальны. Посимвольно пройтись не проблема, но делать это каждый раз при совпадении слишком долго.

Без деталей задачи это просто ещё одна флеймогонная тема.

Быстрая это насколько?

Вот например у меня словарь ~77000 слов. Есть 4 тестовых слова, 2 в словаре есть, 2 в словаре нету. слова 18, 16, 19, 18 символов. Делаю 1000000 итераций поиска примерно такого плана

// test - std::vector<std::string> с 4 словами
// res - int[4]
    for(int i=0; i<1000000; ++i) { // миллион итераций.
        int j=0;
        for( auto &t: test ) {
            .... поиск 
            res[j++] += found;
        }
    }

получаю что этот код выполняется за 570804 микросекунд +-. То есть чуть больше полу секунды.

1000000 - нашел 1000000 раз 
0       - не нашел 
1000000 - нашел 
0       - не нашел
570804

Очевидно, что самый быстрый вариант без нарушений условий задачи.

какие же вы все тут на ЛОРе слабоумные.

https://yandexdataschool.ru/edu-process/courses/algorithms#item-6

Я же написал выше про perfect hashing. Существует метод построения хэш-таблицы для фиксированного множества без колизий, т.е. гарантированный O(1) на lookup.

Видимо, ничтожное умишко не позволяет понять тебе этот материал.

Это правда, нормальных программистов вообще по пальцам пересчитать можно. Стал смотреть это видео и голова закружилась от всей этой математики. Вроде понятия не сложные, но объясняется все очень запутанно.

Vantage-point tree + http://lemire.me/blog/2015/10/26/crazily-fast-hashing-with-carry-less-multipl...

Хеш позволит тебе найти эту строку быстро, потом действительно сравнить. Это проблема?

У тебя каша в голове: хеш в данном случае это индекс в таблице для быстрого поиска, а у таблицы конечный размер, sha1 тут не в тему

тьфу, т.е. имелась ввиду чексума, вроде crc.

Посимвольно пройтись не проблема, но делать это каждый раз при >совпадении слишком долго.

Тебе нужно малое гарантированное время выполнения каждой операции или просто высокое среднее быстродействие?

Можно адаптивно менять хеш-функцию по мере роста дерева, чтобы снижать вероятность совпадения.

Вместо посимвольного использовать побайтное - на такой практической вещи, как преобразование юникода, производительность может хорошо просесть.

А вместо побайтного - разбить на слова максимальной разрядности, которые данный процессор может сравнить.

Можно взять две хеш-функции, одну слабую (простую). Ей сначала сравниваем. Потому сильную (сложную) - ей сравниваем при совпадении простой. Если совпала сложная - сравниваем целиком.