c++ - 如何加快最长公共子串长度的计算？

Question

我有两个非常大的字符串，我正在尝试找出它们的Longest Common Substring。

一种方法是使用后缀树（假设具有非常好的复杂性，尽管实现复杂），另一种是动态编程方法（以上链接的维基百科页面都提到了这两种方法）。

使用动态规划

问题是动态规划方法的运行时间很长（复杂度是O(n*m), wheren和m是两个字符串的长度）。

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

Answer 1

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

一个优化是在空间中（这可能会为您节省一点分配时间）注意到LCSuff它只取决于前一行 - 因此如果您只关心长度，您可以将O(nm)空间优化到O(min(n,m)).

这个想法是只保留两行 - 您正在处理的当前行，以及您刚刚处理的前一行，并丢弃其余行。

Answer 2

在实践中会更快吗？是的。Big-Oh会更快吗？不，动态规划解决方案始终为 O(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 的子串。您可以使用如下多项式公式：

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 的位向量算法可以为您提供帮助。它通过使用位操作来工作，并且是一种更快的方法。