如何使用C++找到最长公共子串

Question

我在网上搜索了一个C++ Longest Common Substring实现,但未能找到一个像样的.我需要一个返回子串本身的LCS算法,因此它不仅仅是LCS.

不过,我想知道如何在多个字符串之间做到这一点.

我的想法是检查两个字符串之间的最长字符串,然后检查所有其他字符串,但这是一个非常缓慢的过程,需要在内存上管理许多长字符串,使我的程序非常慢.

知道如何为多个字符串加速这个吗？谢谢.

重要编辑 我给出的一个变量确定了最长公共子串需要的字符串数,因此我可以给出10个字符串,并找到它们的LCS(K = 10)或LCS为4他们,但我不知道哪个4,我必须找到最好的4.

Answer 1

答案是广义的SUFFIX TREE.http://en.wikipedia.org/wiki/Generalised_suffix_tree

您可以使用多个字符串构建通用后缀树.

看看这个http://en.wikipedia.org/wiki/Longest_common_substring_problem

后缀树可以在每个字符串的O(n)时间内构建,总共为k*O(n).K是字符串的总数.

所以解决这个问题很快.

Answer 2

这是一篇关于有效地查找所有常见子串的优秀文章,其中包含C中的示例.如果您需要的时间最长,这可能是过度的,但它可能比关于后缀树的一般文章更容易理解.