如何使用 trie 在两个或多个字符串中找到 LCS(最长公共子字符串)?
我有这样的想法——假设我的第一个字符串是“abbcabdd”。然后我将首先在 trie 中插入“abbcabdd”,然后是“bbcabdd”,然后是“bcabdd”……,然后是“d”,并对每个字符串重复此过程。
然后通过遍历trie计算最长的子串。
但我认为它效率不高。还有其他改进的方法吗?
如何使用 trie 在两个或多个字符串中找到 LCS(最长公共子字符串)?
我有这样的想法——假设我的第一个字符串是“abbcabdd”。然后我将首先在 trie 中插入“abbcabdd”,然后是“bbcabdd”,然后是“bcabdd”……,然后是“d”,并对每个字符串重复此过程。
然后通过遍历trie计算最长的子串。
但我认为它效率不高。还有其他改进的方法吗?
您所描述的正是后缀树- 使用优化的算法生成后缀树,您将提高效率!
请注意,有一种用于构建后缀树的算法O(n)
(当然,假设是一个常量字母表)。