string - 如何在给定词典中查找所有输入词？

Question

这是 this question. 的后续行动.

如果我有一个字符串 text 和一组其他字符串，我可以使用 Aho-Corasick在 text 中查找集合字符串的算法。

现在我有一个字典(一组字符串)而不是文本。我可以将 dictionary 组织为 trie 或哈希表(甚至 BST)。我可以申请Aho-Corasick吗？在 dictionary 中查找集合中所有字符串的算法？

Answer 1

您可以应用修改后的算法。

假设树中的每个节点有两种类型的边

1)边“可能是”，如果你在前缀处，得到一些字母，那么新前缀仍然可以是字典中某个单词的前缀。

示例:字典 aaa 和 aaabc，如果您在 aaa 并收到字母 b，您将移动到 aaab。

2)边“nope”，如果你在前缀处，得到一些字母，所以新前缀不在字典中，你说那个词不在字典中，然后继续下一个词。

示例:字典 aaa 和 aaabc，如果您在 aaa 并收到字母 c，您可以说该词不在字典中并继续下一个词。

要构建树，您需要 O(字典总长度)时间和 O(长度)来检查每个单词，因此这将导致 O(输入)算法。