如何使用trie在两个或多个字符串中找到lcs(最长公共子字符串)?
我有个这样的主意-
假设我的第一个字符串是“abbcbdd”。
然后我将首先在trie中插入“abbcbdd”,然后插入“bbcabdd”,然后插入“bcabdd”,然后是“d”
对每个字符串重复这个过程。
然后通过遍历trie计算最长的子串。
但我认为这是没有效率的。
还有其他改进方法吗?

最佳答案

你所描述的正是一个suffix tree-使用一个优化的算法生成一个后缀树,你将得到你的效率提高!
注意,在O(n)中有一个构建后缀树的算法(当然,假设是一个常量字母表)。

10-06 04:05
查看更多