Mic*_*ael 10 algorithm data-structures
这是一个访谈问题:查找给定字符串的所有(英语单词)子串.(每一个=每一个,永远,非常).
显然,我们可以循环遍历所有子串并根据英语词典检查每个子串,组织为一组.我相信字典足够小以适应RAM.如何组织字典？至于我记得,原始spell命令加载了一个words文件bitmap,表示一组单词哈希值.我会从那开始.
另一种解决方案是trie从字典构建的.使用trie,我们可以循环遍历所有字符串字符并检查trie每个字符.我猜这个解决方案的复杂性在最坏的情况下是相同的(O(n^2))
是否有意义？你会建议其他解决方案吗？
的阿霍Corasick字符串匹配算法,其"构造一个有限状态机,类似于具有各种内部节点之间的额外连结一线索".
但是所有被认为是"从英语词典中构建一个特里并且对所有字符串的所有后缀进行同时搜索"的内容应该非常适合采访.
我不确定 Trie 能否轻松匹配从字符串中间开始的子词。
具有类似概念的另一个解决方案是使用状态机或正则表达式。正则表达式只是 word1|word2|.... 我不确定标准正则表达式引擎是否可以处理涵盖整个英语语言的表达式，但在给定字典的情况下构建等效的状态机应该不难。
一旦正则表达式被编译\状态机被构建，分析特定字符串的复杂度是 O(n)