如何使用 trie 在两个或多个字符串中找到 LCS(最长公共(public)子字符串)？
我有这样一个想法—— 假设我的第一个字符串是“abbcabdd”。 然后我将首先在 trie 中插入“abbcabdd”，然后是“bbcabdd”，然后是“bcabdd”....，然后是“d” 并对每个字符串重复此过程。
然后通过遍历trie计算出最长的子串。
但我认为效率不高。 还有其他改进方法吗？
最佳答案
你所描述的正是一个suffix tree - 使用优化的算法生成后缀树，您将获得更高的效率!
请注意，在 O(n) 中有一个构建后缀树的算法(当然，假设一个常数字母表)。
关于string - 使用 Trie 查找最长公共(public)子串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12924595/