string - 最长公共(public)子串 : recursive solution?

Question

公共(public)子串算法:

LCS(x,y) = 1+ LCS(x[0...xi-1],y[0...yj-1] if x[xi]==y[yj]
           else 0

现在动态规划解决方案很好理解了。但是我无法找出递归解决方案。如果有多个子字符串，则上述算法似乎会失败。

例如:

x = "LABFQDB" and y = "LABDB"

应用上述算法

1+ (x=  "LABFQD" and y = "LABD")
1+ (x=  "LABFQ" and y = "LAB")
return 0 since 'Q'!='B'

返回的值应该是 2 而我应该是 3？

有人可以指定递归解决方案吗？

Answer 1

尽量避免混淆，你问的是longest common substring，而不是longest common subsequence，它们很相似但是have differences .

The recursive method for finding longest common substring is:
Given A and B as two strings, let m as the last index for A, n as the last index for B.

    if A[m] == B[n] increase the result by 1.
    if A[m] != B[n] :
      compare with A[m -1] and B[n] or
      compare with A[m] and B[n -1] 
    with result reset to 0.

为了更好地说明算法，以下是未应用记忆化的代码。

   public int lcs(int[] A, int[] B, int m, int n, int res) {
        if (m == -1 || n == -1) {
            return res;
        }
        if (A[m] == B[n]) {
            res = lcs(A, B, m - 1, n - 1, res + 1);
        }
        return max(res, max(lcs(A, B, m, n - 1, 0), lcs(A, B, m - 1, n, 0)));
    }

    public int longestCommonSubString(int[] A, int[] B) {
        return lcs(A, B, A.length - 1, B.length - 1, 0);
    }