database - 为大型数据库中的字符串匹配算法构建后缀树

Question

上周我进行了一次实习面试，我收到了一个关于在大型数据库中搜索特定字符串的问题。面试的时候我完全不知道，虽然我只是回复了“多级哈希”，因为这是我知道的唯一一个时间效率最高的hin，经过一番谷歌搜索后，我认为他期望的答案是后缀树。现在，在我的搜索过程中，我找到了构建后缀树的算法，甚至还有关于如何构建后缀树的研究论文！！那么真的有可能实现字符串匹配算法的后缀树，尤其是在面试期间吗？

如果有人可以照亮它，那就太好了。

提前致谢

Answer 1

通常，面试官不需要对这类问题给出准确的答案，他们更感兴趣的是你思考问题并尝试解决问题的方式。

当然，提及解决问题的已知算法将是一个加分项，但我发现很难相信有人会需要“后缀树”作为该问题的答案。

话虽如此，我认为构建后缀树的算法并不容易实现。