Проверка, состоит ли слово из одного или нескольких составных словарных слов

Question

Вот сценарий:

У меня есть массив миллионов случайных строк букв длиной 3-32 и массив слов (словарь).

Мне нужно проверитьесли случайная строка может быть составлена ​​путем объединения 1, 2 или 3 разных словарных слов или нет.

Так как словарные слова будут несколько фиксированными, я могу выполнить любую предварительную обработку для них.

В идеале мне бы хотелось, чтобы что-то оптимизировало скорость поиска, выполняя некоторую предварительную обработку словаря.

На какие структуры данных / алгоритмы мне следует обратить внимание, чтобы реализовать это?

Answer 1

Во-первых, создайте B-дерево, подобное Trie, исходя из ваших требований.Каждый корень будет соответствовать букве.Каждое поддерево 2-го уровня будет содержать все слова, которые можно составить двумя буквами и т. Д.

Затем возьмите свое слово и начните с первой буквы и пройдите вниз по B-Tree Trie до тех пор, пока вы не найдете совпадение, а затем рекурсивно примените этот алгоритм к остальной части слова.Если вы не найдете совпадения в какой-либо точке, вы знаете, что не можете составить слово с помощью concats.

Answer 2

Хранить строки словаря в структуре данных хэшированного набора.Выполните итерацию всех возможных разбиений строки, которую вы хотите проверить на 1, 2 или 3 части, и для каждого такого разделения найдите все части в хэш-наборе.

Answer 3

1. Создайте регулярное выражение, соответствующее каждому слову в вашем словаре.
2. Поставьте вокруг него скобки.
3. Положите + на конец.
4. Скомпилируйте его с любым правильным (на основе DFA) движком регулярных выражений.