Longest Common Substring: recursive solution?

Question

The common substring algorithm :

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

Now the Dynamic Programming solution is well understood. However I am unable to figure out the recursive solution. If there are more than one substrings then the above algorithm seems to fail.

Eg:

x = "LABFQDB" and y = "LABDB"

Applying the above algo

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

The value returned would be 2 where i should have been 3?

Can someone specify a recursive solution?

Solution 1

Try to avoid any confusion, what you're asking is longest common substring, not longest common subsequence, they're quite similar but 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.

The following is the code without applying memoization for better illustrating the algorithm.

   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);
    }

Solution 2

package algo.dynamic;

public class LongestCommonSubstring {

public static void main(String[] args) {
    String a = "LABFQDB";
    String b = "LABDB";
    int maxLcs = lcs(a.toCharArray(), b.toCharArray(), a.length(), b.length(), 0);
    System.out.println(maxLcs);
}

private static int lcs(char[] a, char[] b, int i, int j, int count) {
    if (i == 0 || j == 0)
        return count;
    if (a[i - 1] == b[j - 1]) {
        count = lcs(a, b, i - 1, j - 1, count + 1);
    }
    count = Math.max(count, Math.max(lcs(a, b, i, j - 1, 0), lcs(a, b, i - 1, j, 0)));
    return count;
}

}

Solution 3

Here is the recursive code for LONGEST COMMON SUBSTRING:

int LCS(string str1, string str2, int n, int m, int count)
{
    if (n==0 || m==0)
        return count;
    if (str1[n-1] == str2[m-1])
        return LCS(str1, str2, n-1, m-1, count+1);
    return max(count, max(LCS(str1, str2, n-1, m, 0), LCS(str1, str2, n, m-1, 0)));
}