在N个字符串中查找公共子字符串的算法

我熟悉2个字符串的LCS算法。寻找有关在2..N个字符串中查找常见子字符串的建议。每对中可能有多个常见的子串。在字符串的子集中可以有不同的常用子字符串。在N个字符串中查找公共子字符串的算法

字符串：(ABCDEFGHIJKL) (DEF) (ABCDEF) (BIJKL) (FGH)

常见字符串：

1/2 (DEF) 
1/3 (ABCDEF) 
1/4 (IJKL) 
1/5 (FGH) 
2/3 (DEF)

最长的公共字符串：

1/3 (ABCDEF)

最常见的字符串：

1/2/3 (DEF)

来源

2010-03-10 Dwight Kelly

这是一个需要具有一定性能的算法的ACM竞赛问题吗？ – Roman 2010-03-10 16:23:52

子字符串'F'是不是最常见的，因为它出现在四个字符串中？ – interjay 2010-03-10 16:24:17

这是一个好主意，告诉我们为什么你需要这个，所以我们可以了解我们可以妥协的地方，哪里不能。 – 2010-03-10 16:27:05

这SOR在DNA序列分析中一直都是做事情的东西。你可以找到它的各种算法。列出了一个合理的收集品here。

还有一个蛮力的方法，每子字符串（如果你只对短的感兴趣）制作的表格：形成一个N元树（N = 26代表字母，256代表ASCII）级别，并存储每个节点的计数直方图。如果删除少量使用的节点（为了保持内存需求合理），您最终将得到一个算法，该算法可以找到所有长度为M的子序列，例如输入长度为N * M^2 * log（M）的时间N.如果你把它分成K个单独的字符串，你可以建立树结构，并通过树中的一次读取答案（s）。

来源

2010-03-10 17:15:35

几乎都这么说，这一直被用于计算生物学。然而，“substring/subsequence”的定义往往是模棱两可的（对于非算法专家而言并非如此），我认为在这种情况下，他的问题要求它们是连续的。 – Larry 2010-03-10 18:25:33

后缀树是答案，除非你有真正的大字符串，内存成为一个问题。预期字符串中每个字符的内存使用量为10〜30个字节，以实现良好的实现。还有一些开源实现，这可以让你的工作更轻松。

还有其他一些更具吸引力的算法，但它们很难实现（查找“压缩后缀树”）。

来源

2010-03-10 17:31:48 luispedro

在N个字符串中查找公共子字符串的算法

回答

相关问题