algorithm - 查找给定字符串的所有(英文单词)子字符串

Question

这是采访question :查找给定字符串的所有(英文单词)子字符串。 (每个 = 每个，曾经，非常)。

显然，我们可以遍历所有子字符串，并根据组织为一个集合的英语词典检查每个子字符串。我相信这本字典足够小以适合 RAM。如何组织字典？至于我记得，原来的spell命令加载words文件在一个bitmap中，表示一组单词散列值。我将从那里开始。

另一种解决方案是从字典构建trie。使用 trie，我们可以遍历所有字符串字符并检查每个字符的 trie。我想这个解决方案的复杂性在最坏的情况下是一样的 (O(n^2))

有意义吗？您会建议其他解决方案吗？

Answer 1

Aho-Corasick string matching algorithm它“构建了一个类似于 trie 的有限状态机，在各种内部节点之间有额外的链接。”
但是所有考虑到“从英语词典构建一个 trie 并同时搜索给定字符串的所有后缀”的一切都应该非常适合面试。