如何查找给定字典中的所有输入单词？

2018-06-05 18:18:10

这是这个问题的后续行动..

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

现在我有一个dictionary （字符串集）而不是text 。我可以将dictionary组织为一个trie或散列表（甚至BST）。我可以应用Aho-Corasick算法来查找dictionary所有字符串的字符串吗？

您可以应用修改的算法。

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

1）边缘“可能是”，如果你在前缀，并得到一些字母，所以新的前缀仍然可以在字典中的某个词的前缀。

示例：字典aaa和aaabc，如果您在aaa并收到字母b，则移至aaab。

2）边缘“nope”，如果你在前缀，并得到一些字母，所以新的前缀不在字典中，你说这个单词不是在字典中，并继续下一个单词。

示例：字典aaa和aaabc，如果您在aaa并收到字母c，则可以说该字词不是在字典中，然后转到下一个字词。

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

字典的一点是，它有助于通过采用的数据结构进行搜索。

例如，使用散列表，您可以使用散列查找来检查散列表中的每个集合的成员。不需要使用子字符串搜索。

链接地址: http://www.djcxy.com/p/18137.html