查找使用特里最长公共子 [英] Finding longest common substring using Trie

问题描述

我怎样才能找到LCS（最长公共子）使用特里两个或多个字符串中？

How can i find LCS (longest common substring) among two or more strings using trie ?

我有这样一个想法 - 假设我的第一个字符串为abbcabdd。 然后我会先插入线索abbcabdd，然后选择bbcabdd，然后选择bcabdd......，然后是D 重复此过程为每个字符串。

I have an idea like this - suppose my first string is "abbcabdd". then i will first insert "abbcabdd" in trie ,then "bbcabdd", then "bcabdd" .... , then "d" and repeat this process for every string .

然后通过遍历线索计算最长的子串。

Then calculate the longest substring by traversing the trie.

但我认为它是没有效率。 是否有任何其他改进的方法？

but i think it is not efficient. Is there any other improved method ?

推荐答案

你所描述的究竟是什么一个后缀树 - 使用优化生成一个后缀树算法，以及你会得到你的效率提高。

What you are describing is exactly a suffix tree - Use an algorithm optimized to generate a suffix tree, and you will get your efficiency increased!

请注意，有一个算法构建后缀树 O（N）（假设恒定的字母，当然）。

Note that there is an algorithm for building a suffix tree in O(n) (assuming a constant alphabet, of course).

这篇关于查找使用特里最长公共子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！