如何加快最长常见基因长度的计算？

Question

我有两个 非常大的字符串 我试图找出他们的 最长的常见基因.

一种方法是使用 后缀树 （尽管实现了复杂，但应该具有非常好的复杂性），另一个是 动态编程方法 （两者都在上面链接的Wikipedia页面上提到）。

使用动态编程

问题是动态编程方法的运行时间很大（复杂性是 O(n*m), ， 在哪里 n 和 m 是两个字符串的长度）。

我想知道的（在跳到实现后缀树之前）： 如果我只想知道共同的底带的长度（而不是共同的子字符串本身），是否可以加快算法加快算法？

Answer 1

在实践中会更快吗？是的。关于大哦，会更快吗？否。动态编程解决方案始终为O（N*M）。

后缀树可能会遇到的问题是，您可以将后缀树的线性时间扫描换成巨大的太空罚款。后缀树通常比您需要为该算法的动态编程版本实现的表大得多。根据字符串的长度，动态编程完全可能会更快。

祝你好运 ：）

Answer 2

这些会使它运行得更快，尽管它仍然会 O(nm).

一种优化是在太空中（可能会节省一些分配时间）正在注意到 LCSuff 仅取决于上一行 - 因此，如果您只关心长度，则可以优化 O(nm) 空间到 O(min(n,m)).

这个想法是仅保留两行 - 您正在处理的当前行，以及您刚刚处理的上一行，然后扔掉其余的行。

Answer 3

这是一种简单的算法，可以在O（（m+n）*log（m+n））中完成，并且与o（m+n）运行时的后缀树算法相比，实现了得多。

让它从最小公共长度（minl）= 0开始，最大公共长度（maxl）= min（m+n）+1。

1. if (minL == maxL - 1), the algorithm finished with common len = minL.

2. let L = (minL + maxL)/2

3. hash every substring of length L in S, with key = hash, val = startIndex.

4. hash every substring of length L in T, with key = hash, val = startIndex. check if any hash collision in to hashes. if yes. check whether whether they are really common substring. 

5. if there're really common substring of length L, set minL = L, otherwise set maxL = L. goto 1.

剩下的问题是如何在时间o（n）中使用长度为l的所有substring。您可以使用多项式公式如下：

Hash(string s, offset i, length L) = s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[i+L-2] * p + s[i+L-1]; choose any constant prime number p.

then Hash(s, i+1, L) = Hash(s, i, L) * p - s[i] * p^L + s[i+L];

Answer 4

Myer的位矢量算法 可以帮你。它通过使用位操作来起作用，并且是一种更快的方法。