为什么我们在最长公共子串中 return max({count,v1,v2})

Question

为什么我们 return max({count,v1,v2}) 在最长公共子串中，因为我先做最长公共子序列，然后做最长公共子串，但像在最长公共子序列中一样感到困惑如果 x[n-1] == y[m-1] 那么我 return 但是在最长公共子串的情况下我没有 return 值而是我等待其他 2 个递归调用然后 return 最大。我真的很困惑。

Answer 1

在 LC-Subsequence 算法中，我们增加了调用者的计数，因为计数的聚合可以发生在树下的级别中，这些级别不一定需要是该树的直接子级 - 在其他情况下换句话说，我们可以跳过级别，直到找到下一个匹配项，而计数是我们找到匹配项的这些级别的聚合。这里不求停产。

ex: x: a,b,c,d,e,f
    y: a,b,f,c,e
    lc-subsequence: a,b,c,e
    max: 4
here you can jump from b -> c in string y. Similarly, c -> e in string x.

但在 LC-Substring 的情况下，我们将计数传递到下一个级别，因为当且仅当我们在紧接的下一个级别有匹配项时，我们才想增加计数。也就是这里我们找停产。

 ex: x: a,b,c,d,e,f
        y: a,b,f,c,e
        lc-substring: a,b | c | e 
        max: 2
here you can't jump from b -> c in string y and and c->e in string x respectively.

因此，count表示在字符串x和y中都完全匹配的字符串。这就是为什么你取最大值 (count,v1,v2)

为什么我们在最长公共子串中 return max({count,v1,v2})

Why we return max({count,v1,v2}) in Longest Common Substring

string

dynamic-programming