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

Question

Это интервью вопрос : Найти все (английские слова) подстроки данной строки. (каждый = каждый, всегда, очень).

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

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

Имеет ли это смысл? Вы бы предложили другие решения?

Answer 1

Алгоритм сопоставления строк Aho-Corasick , который "создает конечный автомат, который напоминает дерево с дополнительными связями между различными внутренними узлами".
Но все считалось "построить дерево изАнглийский словарь и одновременный поиск по нему всех суффиксов заданной строки "должен быть довольно хорош для собеседования.

Answer 2

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

Answer 3

Я не уверен, что Trie будет легко работать для сопоставления подслов, начинающихся в середине строки.

Другое решение с аналогичной концепцией - использовать конечный автомат или регулярное выражение.регулярное выражение - это просто word1 | word2 | .... Я не уверен, что стандартные движки регулярных выражений могут обрабатывать выражения, охватывающие весь английский язык, но не должно быть сложно построить эквивалентный конечный автомат с учетом словаря.

Как только регулярное выражение скомпилировано \ конечный автомат построен, сложность анализа конкретной строки составляет O (n)