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

Question

我熟悉2个字符串的LCS算法.寻找在2..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)

Answer 1

这种事情一直在DNA序列分析中完成.您可以找到各种算法.这里列出了一个合理的收藏.

还有蛮力的方法来制作每个子串的表(如果你只对短的子句感兴趣):在每个级别形成一个N元树(N = 26表示字母,256表示ASCII),并存储直方图每个节点的计数.如果你删除很少使用的节点(为了保持内存需求合理),你最终得到一个算法,它可以找到长度达到M的所有子序列,例如N*M ^ 2*log(M)时间,用于输入长度N.如果您将其拆分为K个单独的字符串,则可以构建树结构,并在一次通过树中读取答案.