我有两个非常大的字符串，我想找出它们的 Longest Common Substring .
一种方法是使用后缀树(应该有很好的复杂性，虽然实现起来很复杂)，另一种是动态规划方法(都提到了在上面链接的维基百科页面上)。
使用动态规划
问题在于动态规划方法运行时间巨大(复杂度为O(n*m)，其中n和m 是两个字符串的长度)。
我想知道的(在跳转到实现后缀树之前):如果我只想知道公共(public)子串的长度(而不是公共(public)子串本身)，是否可以加快算法速度？
最佳答案
这些将使它运行得更快，尽管它仍然是 O(nm)。
空间优化(这可能会为您节省一点分配时间)注意到 LCSuff 仅依赖于前一行——因此，如果您只关心长度，则可以优化O(nm) 空间缩小到 O(min(n,m))。
想法是只保留两行——您正在处理的当前行和您刚刚处理的前一行，然后丢弃其余行。
关于c++ - 如何加快计算最长公共(public)子串的长度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2710010/