Find longest common subsequence of 2 String?

Question

I'm learning about the longest common subsequence, Using these algorithm:

---

public class LCS {

static int[][] E;
static int[][] S;
static int D;
static int T;
static int L;
public static void LCS_cost(String X,String Y)
{       
    int m = X.length();
    int n = Y.length();
    E = new int[m][n];
    S = new int[m][n];
    for(int i=0;i<m;i++){
        E[i][0] = 0;
    }
    for(int j=0;j<n;j++){
        E[0][j] = 0;
    }
    for(int i=1;i<m+1;i++){
        for(int j=1;j<n+1;j++){
            if(X.charAt(i) == Y.charAt(j)){
                E[i][j] = E[i-1][j-1]+1;
                D =  E[i-1][j-1]+1;
                S[i][j] = D;//Diagonal Direction    
            }
            else if (E[i-1][j]>=E[i][j-1]){
                    E[i][j] = E[i-1][j];
                    T = E[i-1][j];
                    S[i][j] = T;//TOP
            }
            else
                    E[i][j] = E[i][j-1];
                    L = E[i][j-1];
                    S[i][j] = L;//Left
        }
    }

}

public static void Backtrack(int[][] S,String X,String Y){
int row = X.length();
int col = Y.length();   

while (row > 0 || col > 0){
    if (S[row][col] == D){
        System.out.print(X.charAt(row));
        row--;
        col--;
    }
    else if (S[row][col] == T){
        row--;
    }
    else
        col--;
}
}
public static void main(String[] args) {
    new  LCS();
    LCS_cost("SCHOOL","SPOOL");
    Backtrack(S,"SCHOOL", "SPOOL");
    }
}

But the program return an ErrorCharAt(Unknow Source) and didn't do anything.

i'm trying to change

for(int i=1;i<m+1;i++){
        for(int j=1;j<n+1;j++){

to

for(int i=1;i<m;i++){
        for(int j=1;j<n;j++){

the result is this line IndexOutofBoud

if (S[row][col] == D){
    ....
    }

Also,if i change int i and j to 0 then E below would be index -1 and error

for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(X.charAt(i) == Y.charAt(j)){
                E[i][j] = E[i-1][i-1]+1;
                ......
            }

i'm so lost right now.Can anyone help me?

Answer 1

I would go about this using strings rather than dealing with individual characters:

String findLCS(String str1, String str2) {
    int longest = 0;
    String longestSubstring = "";

    for (int i=0; i < str1.length(); ++i) {
        for (int j=i+1; j <= str1.length(); ++j) {
            String substring = str1.substring(i, j);
            if (str2.contains(substring) && substring.length() > longest) {
                longest = substring.length();
                longestSubstring = substring;
            }
        }
    }

    return longestSubstring;
}

As you can see, using String.contains() is more powerful than it looks.

Answer 2

If

 int m = X.length();

then

for(int i=1;i<m+1;i++){
   ...
   if(X.charAt(i) ....

will throw an error as in Java arrays are zero based

Also if

int row = X.length();
int col = Y.length(); 

if (S[row][col] == D){

will throw an error

Also, use String.equals to compare Strings not ==

Answer 3

import java.util.Scanner; class Main {

public static void main(String[] args)
{


Scanner sc=new Scanner(System.in);




    Sub s=new Sub();

    int t=Integer.parseInt(sc.nextLine());

    for(int i=1;i<=t;i++)
    {




    String a=sc.next();
    String b=sc.next();

    System.out.println("Case "+i+": "+s.subString(a, b));


}

}

} class Sub {

   public static int subString (String a,String b)
   {

       int max=0;
       int m=a.length();
       int n=b.length();

       int dp[][]=new int [m][n];

       for(int i=0;i<m;i++)
       {

           for(int j=0;j<n;j++)
           {

               if(a.charAt(i)==b.charAt(j))

               {
                   if(i==0||j==0)
                   {
                       dp[i][j]=1;
                   }
                   else 
                       dp[i][j]=dp[i-1][j-1]+1;
               }

               if(max<dp[i][j])

                   max=dp[i][j];
           }


       }


       return max;

   }

}

Answer 4

You are using a matrix approach where we,

• In case [i]th char & [j]th char matches - go previous diagonally [i-1][j-1] value and add 1 for lcs length
• In case [i]th char & [j]th char don't match - then take max value of {left [i][j-1] or right [i-1][j] for lcs.

Personally I feel this approach is more scripted and essence of Dynamic Programming & Memorization shed behind it. When we are more relying on script approach rather than pure logic of DP & memo - we are more prone to error or may be lost in between...

Rather than matrix approach I have used Dynamic Programming and memoization to demonstrate LCS as -

package com.company.dynamicProgramming;

import java.util.HashMap;
import java.util.Map;

public class LongestCommonSubsequnce {


    public static void main(String ...args){

        String s1 = "SCHOOL";
        String s2 = "SPOOL";
        System.out.println(new StringBuilder(findLcs(s1, s2, new HashMap<>())).reverse());
    }



    static String findLcs(String s1, String s2, Map<String, String> memo){

        //check if lcs is already processed in memo for s1 & s2
        String lcs = memo.get(s1+"-"+s2);
        if(lcs != null){
            return lcs;
        }


        if (s1.substring(s1.length()-1).equals(s2.substring(s2.length()-1))){
            lcs = s1.substring(s1.length()-1);
            if(s1.length()>1 && s2.length()>1){
                lcs = lcs + findLcs(s1.substring(0, s1.length()-1), s2.substring(0, s2.length()-1), memo);
                memo.put(s1.substring(0, s1.length()-1)+ "-" + s2.substring(0, s2.length()-1), lcs);
            }
            else {
                memo.put(s1+"-"+s1, lcs);
            }
            return lcs;

        }else {

            String lcs1="";
            String lcs2="";

            if(s1.length()>1 && s2.length()>1){
                lcs1 = findLcs(s1.substring(0, s1.length()-1), s2, memo);
                memo.put(s1.substring(0, s1.length()-1)+"-"+s2, lcs1);
                lcs2 = findLcs(s1,s2.substring(0, s2.length()-1),memo);
                memo.put(s1 +"-"+s2.substring(0, s2.length()-1), lcs2);
            }
            else if(s1.length()>1){
                lcs1 = findLcs(s1.substring(0, s1.length()-1), s2, memo);
                memo.put(s1.substring(0, s1.length()-1)+"-"+s2, lcs1);
            }
            else if(s2.length()>1){
                lcs2 = findLcs(s1,s2.substring(0, s2.length()-1),memo);
                memo.put(s1 +"-"+s2.substring(0, s2.length()-1), lcs2);
            }else {
                memo.put(s1+"-"+s2,"");
            }

            if(lcs1.length() >= lcs2.length()){
                return lcs1;
            }else {
                return lcs2;
            }
        }
    }
}

Run this code and result is -

SOOL

Process finished with exit code 0