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

Question

我有两个非常大的字符串，我想找出它们的 Longest Common Substring .

一种方法是使用后缀树(应该有很好的复杂性，虽然实现起来很复杂)，另一种是动态规划方法(都提到了在上面链接的维基百科页面上)。

使用动态规划

问题在于动态规划方法运行时间巨大(复杂度为O(n*m)，其中n和m 是两个字符串的长度)。

我想知道的(在跳转到实现后缀树之前):如果我只想知道公共(public)子串的长度(而不是公共(public)子串本身)，是否可以加快算法速度？

Answer 1

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

空间优化(这可能会为您节省一点分配时间)注意到 LCSuff 仅依赖于前一行——因此，如果您只关心长度，则可以优化O(nm) 空间缩小到 O(min(n,m))。

想法是只保留两行——您正在处理的当前行和您刚刚处理的前一行，然后丢弃其余行。