Вот так

Для такого бора алгоритм обязан работать корректно

Начинает с корня, в левом поддереве 4 листа, значит идет вправо (2-й бит 1), в левом поддереве 2 листа, значит идет вправо (1-й бит 1), в левом поддереве 1 лист, значит идет вправо (0-й бит 1)
Ответ 00000111 или 7

Люди, у меня вопрос. Мне нужно по нескольким десяткам тысяч строк искать отдельные строки.
причем правило такое что если есть строка
"Моя длинная строка"
то запрос
"ояннк" должен находить эту строку потому что эти буквы там встречаются именно в таком порядке.
"Моя длинная строка"
я пока вижу только вариант для каждой отдельной строки во всём наборе идти по строке и сравнивать буквы по очереди.
А нет варианта как-то это ускорить или построить индекс? Если да, то в какую сторону копать?

Может для этого есть какой-то готовый известный алгоритм

делаешь регулярное выражение о.*я.*н.*н.*к, прогоняешь

это равносильно тому что я написал. проверить каждую строку

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

вроде регулярки на множественных строках можно ускорять суффиксными деревьями

регулярки же NDFA

можно ж детерминизировать

получишь неполином состояния

F, что тут сказать

но это неполином от регулярки, а не от количества строк, по которым надо пройтись

может иметь смысл

учитывая что подпоследовательности за произведение длин при подготовке, очень сомневаюсь

в смысле за количество умножить на сумму длин

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

Спасибо!

тут беда в том, что в случае, если не нашлось, оно будет очень долго мучать