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?

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

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

}

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

Answer 4

long max_sub(int i, int j)
{

    if(i<0 or j<0)
        return 0;

    if(s[i]==p[j])
    {
        if(dp[i][j]==-1)
          dp[i][j]=1+max_sub(i-1,j-1);
    }
    else
    {
        dp[i][j] = 0;
    }
    if(i-1>=0 and dp[i-1][j]==-1)
        max_sub(i-1, j);
    if(j-1>=0 and dp[i][j-1]==-1)
        max_sub(i, j-1);
    return dp[i][j];
}

The problem with your code seems like you are not trying all the n^2 possibilities.

Answer 5

I designed a recursive solution for this in c++. In my approach i am taking a particular i,j and then if they are equal i am adding 1 and calling the function for i+1, j+1, while if they aren`t equal i am storing a zero at the corresponding i, j in the 2D array that i have created. After its execution i am printing the 2D array and it seems to be okay. As i am just filling the 2D array i think the time complexity must be O(mn) where m is the length of one array and n is of another array.

//Finding longestcommonsubword using top down approach [memoization]
#include<iostream>
using namespace std;

int findlength(char A[], char B[], int i, int j, int st[][5], int r, int c){

if(r <= i)
  return 0;
else if(c <= j)
  return 0;
else{
    if(A[i] == B[j]){

        if(st[i][j] == -1)
        st[i][j] = 1+findlength(A, B, i+1, j+1, st, r, c);
    }else{
        st[i][j] = 0;
        int a = findlength(A, B, i, j+1, st, r, c);
        int b = findlength(A, B, i+1, j, st, r, c);
    }
}    

return st[i][j];
}

int main(){
int n,m;
cin>>n>>m;
char A[n],B[m];

for(int i = 0;i < n;i++)
  cin>>A[i];

for(int j = 0;j < m;j++)
  cin>>B[j];

int st[n][5];


for(int k = 0; k < n;k++){
    for(int l = 0; l< 5;l++){
       st[k][l] = -1;   
    }
}
findlength(A, B, 0, 0, st, n, 5);

for(int k = 0; k < n;k++){
    for(int l = 0; l< 5;l++){
      cout<<st[k][l]<<" ";
    }
    cout<<endl;
}

return 0;
}

Answer 6

     int max; //This gloabal variable stores max substring length
     int[][]dp; // 2D Array for Memoization

     void main(){
     //--------Main method just intended to demonstrate initialization---------

     dp = new int[m+1][n+1] //m and n are string length
     lcs(String a,String b,int n,int m)
     }
     
     //---++++++++-----Recrsive Memoized Function------++++++++++++-------
     static int lcs(String a,String b,int n,int m){
     
     if(dp[n][m]!=-1)return dp[n][m];
    
     if(n==0||m==0)return dp[n][m]=0;
     
     
     if(a.charAt(n-1)==b.charAt(m-1))
     {
        int res=0;int i=n-1,j=m-1;
        while((i>=0&&j>=0)&&a.charAt(i)==b.charAt(j)){
            res++;
            if(i==0||j==0)return dp[n][m] = Math.max(res,max);
            i--;j--;
        }
        max=Math.max(res,max);
        
        return dp[n][m]=Math.max(max,Math.max(lcs(a,b,n-res,m),lcs(a,b,n,m-res)));
         
     }
     
     return dp[n][m]=Math.max(lcs(a,b,n-1,m),lcs(a,b,n,m-1));
     
     
     
 }

Answer 7

Below is the recursive approach for calculating the longest common string:

public int lcsLength(String x, String y)
{
    char[] xc = x.toCharArray();
    char[] yc = y.toCharArray();

    return lcsLength(xc, xc.length - 1, yc, yc.length - 1, 0);
}

private int lcsLength(char[] xc, int xn, char[] yc, int yn, int currentCsLength)
{
    if (xn < 0 || yn < 0) {
        return currentCsLength;
    }
    if (xc[xn] == yc[yn]) {
        return lcsLength(xc, xn - 1, yc, yn - 1, currentCsLength + 1);
    }
    else {
        return max(currentCsLength,
                max(
                        lcsLength(xc, xn - 1, yc, yn, 0),
                        lcsLength(xc, xn, yc, yn - 1, 0)));
    }
}

The downside of using this solution is that it is suffering from recalculating several times the common string for the same substrings of x and y.

This solution is using memoization technique to avoid calculating several times the longest common string in the recursion.

public int lcsLength(String x, String y)
{
    char[] xc = x.toCharArray();
    char[] yc = y.toCharArray();

    Integer[][] memoization = new Integer[xc.length][yc.length];

    return lcsLength(xc, xc.length - 1, yc, yc.length - 1, memoization);
}

private int lcsLength(char[] xc, int xn, char[] yc, int yn, Integer[][] memoization)
{
    if (xn < 0 || yn < 0) {
        return 0;
    }
    if (memoization[xn][yn] == null) {
        if (xc[xn] == yc[yn]) {
            // find out how long this common subsequence is
            int i = xn - 1, j = yn - 1, length = 1;
            while (i >= 0 && j >= 0 && xc[i] == yc[j]) {
                i--;
                j--;
                length++;
            }
            memoization[xn][yn] = Math.max(length, lcsLength(xc, xn - length, yc, yn - length, memoization));
        }
        else {
            memoization[xn][yn] = max(
                    lcsLength(xc, xn - 1, yc, yn, memoization),
                    lcsLength(xc, xn, yc, yn - 1, memoization));
        }
    }

    return memoization[xn][yn];
}

Answer 8

Hope this might help,even though there are bunch of answers!

 public static int LongestCommonSubString(String x, String y, int m, int n, int curr_max) {
        if (m == 0 || n == 0) return curr_max;

        if (x.charAt(m - 1) == y.charAt(n - 1)) return LongestCommonSubString(x, y, m - 1, n - 1, curr_max + 1);
        
        return Math.max(LongestCommonSubString(x, y, m - 1, n, 0), LongestCommonSubString(x, y, m, n - 1, 0));
    }

Answer 9

import sun.jvm.hotspot.types.CIntegerType;

class RespObject {
    public int len;
    public boolean isSubString;
    int maxLen;

    public RespObject(int len, boolean isSubString, int maxLen) {
        this.maxLen = maxLen;
        this.len = len;
        this.isSubString = isSubString;
    }
}

public class LongestCommonSubstring {
    public static void longestCommonSubstring(String str1, String str2, int i, int j, RespObject resp) {
        if ((j == str2.length()) || (i == str1.length())) {
            resp.isSubString = false;
            resp.len = 0;
            return;
        }
        int currLen = 0;
        longestCommonSubstring(str1, str2, i + 1, j, resp);
        RespObject respObject1 = resp;
        longestCommonSubstring(str1, str2, i, j + 1, resp);
        RespObject respObject2 = resp;
        if (str1.charAt(i) == str2.charAt(j)) {
            longestCommonSubstring(str1, str2, i + 1, j + 1, resp);
            resp.len += 1;
            currLen = resp.len;
            resp.isSubString = true;
        } else {
            resp.len = 0;
            resp.isSubString = false;
        }
        resp.maxLen = Integer.max(Integer.max(respObject1.maxLen, respObject2.maxLen), currLen);
    }

    public static void main(String[] args) {
        RespObject respObject = new RespObject(0, false, Integer.MIN_VALUE);
        longestCommonSubstring("dSite:Geeksf", "wSite:GeeksQ", 0, 0, respObject);
        System.out.println(respObject.len + "   " + String.valueOf(respObject.isSubString) + "  " + respObject.maxLen);
    }
}