Как найти все входные слова в данном словаре?

Question

Это продолжение этого вопроса. .

Если у меня есть строка text и набор других строк, я могу использовать алгоритм Aho-Corasick , чтобы найти строки набора в text.

Теперь у меня есть dictionary (набор строк) вместо text.Я могу организовать dictionary как три или хеш-таблицу (или даже BST).Могу ли я применить алгоритм Aho-Corasick , чтобы найти все строки набора в dictionary?

Answer 1

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

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

Answer 2

Вы можете применить модифицированный алгоритм.

Предположим, что у каждого узла в дереве есть 2 типа ребер

1) Край "может быть", если вы находитесь в префиксе, и получите некоторую букву,поэтому новый префикс все еще может быть префиксом из некоторого слова в словаре.

Пример: Словарь aaa и aaabc, если вы находитесь в aaa и получаете букву b, вы переходите в aaab.

2) Край "nope", если вы находитесь по префиксу и получаете какую-то букву, поэтому новый префикс отсутствует в словаре, вы говорите, что этого слова нет в словаре, и переходите к следующему слову.

Пример: Словарь aaa и aaabc, если вы находитесь в aaa и получаете букву c, вы можете сказать, что этого слова нет в словаре и перейти к следующему слову.

Чтобы построить дерево, вы 'Вам понадобится время O (общая длина словаря) и O (длина), чтобы проверить каждое слово, так что это приведет к алгоритму O (ввод).