Найти все (английские слова) подстроки заданной строки

Это интервью вопрос : Найти все (английские слова) подстроки заданной строки. (every = every, ever, very.)

Очевидно, мы можем перебрать все подстроки и проверить каждую по английскому словарю, организованному в виде набора. Я считаю, что словарь достаточно мал, чтобы вместить ОЗУ. Как организовать словарь? Насколько я помню, исходная команда spell загружала файл слов в битовую карту , представляя набор хеш-значений слов. Я бы начал с этого.

Другое решение - это дерево , построенное на основе словаря. Используя дерево, мы можем перебрать все строковые символы и проверить дерево для каждого символа. Я предполагаю, что сложность этого решения будет такой же в худшем случае ( O (n ^ 2) )

Есть ли в этом смысл? Не могли бы вы предложить другие решения?