Find Longest common subsequence : my method [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 9 years ago.

I am trying to implement the Longest common sub sequence of 2 strings. My method is bit different than posted here. I am near the solution but little problem. Please help me.

My problem: Desired Output: metallica current output: etallica

My code is :

import java.util.ArrayList;
import java.util.Stack;

public class CommonSubS  {

public static void main(String[] args) {

   ArrayList<Character> ss = new ArrayList<>();
   String s1 = "metallicarules";
   String s2 = "rulmetallicales";
   ArrayList<ArrayList<Character>> one = new ArrayList<>();
   char[] first = s1.toCharArray();
   char[] second = s2.toCharArray();
   int j = 0;
   int current = 0;
   int mainIndex = 0;
   ArrayList<Character> sec = new ArrayList<>();

   // search for each char in second            
   for(int i = 0; i<second.length; i++)
   {    
       j = current;
       // search for each char in first
       while(j<first.length)
       {
           // if match found, add to the arraylist
           if(first[j] == second[i]){

               sec.add(first[j]);
               current = j+1;
               break;
           }
           else 
           {   // if different char occured in between,
               // save current arraylist in one
               // and go forward
               one.add(sec);
               sec = new ArrayList<>();
               j++; 
               current = 0;        
           }

       }
   }

   for(ArrayList<Character> s: one)
   {
       for(Character c: s)
       {
           System.out.print(c);
       }
       System.out.println();    
    }

  }
}

/*
 desired output: metallica
current output: etallica
*/

I know there are other methods but I tried to implement using simple method. Please point out the problem.

Answer 1

I think that the problem is that your i gets incremented and compares the m from metallica of the second word with the last e of the first word, so next iteration it will start from the next letter which is the e (of the second word), that is why you are not getting the m at the beginning. Maybe if you use an i = i-1 every time you ended a common subsequence.

Answer 2

I'm still not exactly sure how your algorithm works, but I think the value of j is getting too large too soon. I changed your else block to reset j to 0 each time, and the code now produces the desired output of "metallica".

           else 
           {   // if different char occured in between,
               // save current arraylist in one
               // and go forward
               one.add(sec);
               sec = new ArrayList<>();
               j = 0; // Start checking from the beginning of the string
               current = 0;
               break; // This will exit the while loop and move on to the next value of i
           }