Solved

Longest common subsequence

Posted on 2011-03-07
11
1,064 Views
Last Modified: 2012-05-11
I have a programming assignment that I have to implement the algorithm for solving the Longest Common Subsequence problem.
the program has to be
•prompts the user to enter a pair of strings
•displays the LCS table produced by the algorithm
•displays the longest common subsequence found
•allows the user to repeat the process with a new pair of strings

This is what I have so far... It compilied but get stoped after I enter two strings...
Could you help me out please?


import java.util.*;

public class LCS 
{
    static Scanner console = new Scanner(System.in);
    
    public static void main(String[] args) 
    {
        int i,j;
        String X;  /* String X */
        String Y;    /* String Y */
        System.out.println("Enter the pair of strings");
        X = console.next();
        Y = console.next();
        System.out.println();
        
        int m = X.length();
        int n = Y.length();
        int[][] T = new int[m+1][n+1];
      
        // C[i][0] = 0 for 0 to m 
        for (i = 0; i <= m; i++) 
        {
            T[i][0] = 0;
        }
	
        // C[0][j] = 0 for  j=0 to n 
        for (j = 0; j <= n; j++) 
        {
            T[0][j] = 0;
        }
        
        //FOR i = 1 TO m
        for (i = 1; i <= m; i++) 
        {
            for (j = 1; j <= n; j++) // FOR i = 1 TO n 
            {
                if (X.charAt(i-1) == Y.charAt(j-1)) 
                    T[i][j]=T[i-1][j-1]+1;
                    else 
                    {	
                    	    T[i][j]=java.lang.Math.max(T[i][j-1],T[i-1][j]);
                    	    
                    }
                }
        }
     	  
        // Backtracking 
        String lcs = new String();
        i=m;
        j=n;
        while (i!=0 && j!=0) 
        {
            if (T[i][j] ==1) 
            {    // diagonal 
            	lcs =X.charAt(i-1) + lcs;
                i = i - 1;
                j = j - 1;
            }
            if (T[i][j] == 2) 
            {  // up 
                i = i - 1;
            }
            if (T[i][j] == 3) 
            {  // backword 
                j = j - 1;
            }
        }
     
        /* print out the result */
        System.out.println("String X is " + X);
        System.out.println("String Y is " + Y);
        System.out.println("The length of LCS is " + T[n][m]);
        System.out.println("The LCS is " + lcs);
        System.out.println(T[i][j]);
         
    }
         
}

Open in new window

0
Comment
Question by:slritmmi
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
11 Comments
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 35063110
Can you step through the code line by line with a debugger?

If not, put in some debugging output lines like this until you see where it is getting stuck.
System.out.println("I got to line 23, i = " + i + " and j = " + j);
0
 
LVL 37

Accepted Solution

by:
TommySzalapski earned 500 total points
ID: 35063128
I think your problem is in the while loop.
You only check if T[i ][j] is 1, 2, or 3. You need to also check for other things.
Also, if T[i ][j] ==1, you check the next one before restarting the loop.
            if (T[i][j] ==1) 
            {    // diagonal 
            	lcs =X.charAt(i-1) + lcs;
                i = i - 1;
                j = j - 1;
            }
            else if (T[i][j] == 2) 
            {  // up 
                i = i - 1;
            }
            else if (T[i][j] == 3) 
            {  // backword 
                j = j - 1;
            }
            else
            {
              System.out.println("Is this an error?, i = " + i + " and j = " + j + " and T[i][j] = " + T[i][j]);
            }

Open in new window

0
 
LVL 36

Expert Comment

by:mccarl
ID: 35063137
Without trying to totally understand your algorithm, from some simple debugging I can see that many of the elements of T[][] are zero after loops at lines 34-46. However, in the last loop at lines 52-68, you are never doing any action if the current element T[ i ][ j ] is zero, and because you never do anything, i and j stay the same, which means the current element will always be the same zero and you will never exit the loop!

BTW, also just an additional point, the t[][] array will always be initialised to be all zeros for you (by Java), no need to do it again at lines 21-31.
0
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 5

Expert Comment

by:Kendor
ID: 35095261
Seems like we had to implement exactly the same thing... (Pattern Recognition 2?)
check out my version of your code...

ps. I am aware that if [option] is not given in the command line that the script fails as it assignes args[1] and args[2]...
public class StringCompare {

	public static void main(String[] args) {
		
		if(args.length > 3 || args.length < 2){
			System.err.println("Check the arguments!");
			System.err.println("usage: java StringCompare [option] x y" +
					"\n options:"+
					"\n 0 -- compute string edit distance between x and y (default)" +
					"\n 1 -- compute longest common subsequence of x and y");
			System.exit(1);
		}
		
		String x = args[1];
		String y = args[2];
		
		int[] c = {2,1,1};	/* Costs: Substitute s,Delete d,Insert i */
		int i,j = 0;
		
		int n = x.length();
		int m = y.length();
		int[][] D = new int[n+1][m+1];;			/* Cost Matrix */
		char[][] pointer = new char[n+1][m+1];	
		
		/* Calculate cost matrix as described in the script*/
		D[0][0] = 0;
		for(i = 1; i<=n; i++){ D[i][0] = D[i-1][0] + c[1]; }
		for(j = 1; j<=m; j++){ D[0][j] = D[0][j-1] + c[2]; }
		
		for(i = 1; i<=n; i++){
			for(j = 1; j<=m; j++){
				
				int m1 = D[i-1][j-1];
				if(x.charAt(i-1) != y.charAt(j-1)){
					m1 = m1 +c[0]; 
				}
				
				int m2 = D[i-1][j] + c[1];
				int m3 = D[i][j-1] + c[2];
				
				D[i][j] = Math.min(Math.min(m1,m2),m3);
				
				/* the bookkeeping part */
				if (m1 == D[i][j]) { 	  pointer[i][j]='s';}
				else if (m2 == D[i][j]) { pointer[i][j]='d';}
				else pointer[i][j]='i';
			}
		}
		
		/* Option 1 selected - do the LCS backtrace */
		if(args[0].charAt(0)=='1'){ 

			/* Backtrace to find LCS */
			StringBuffer theLCS = new StringBuffer();
			
			i=n; j=m; /* start from last */
			while(j>0 && i>0){
				if(x.charAt(i-1) == y.charAt(j-1)) theLCS.insert(0, y.charAt(j-1));
				/* decide on how to go to the next */
				switch (pointer[i][j]) {
				  case 'd': i--;      break; /* delete operation -> go up */
				  case 's': i--; j--; break; /* substitution -> go up and left */
				  case 'i': j--;      break; /* insert operation -> go left */
				  default: break;
				} 
			}

			System.out.println(theLCS.toString());
			
		/* Option 0 selected or default - echo the editdistance of x and y */
		} else {
			System.out.println(D[n][m]);
		}
	}
}

Open in new window

0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 35097354
Kendor, note in the original question that the Asker stated that this was a programming assignment to implement an algorithm.
Your solution no doubt solves the problem but there are two main issues:
1. slritmmi didn't write it so it is academic dishonesty
2. slritmmi won't learn anything if he just uses your code so he'll do poorly on future assignments or fail the tests.

As experts we need to pay attention to see if questions are academic in nature (which slritmmi fortunately told us; a lot of askers don't know to tell us). If it is, we are to guide the asker to the find the solution as much on his own as possible.

Congrats on reaching Master, by the way, and welcome to EE.
0
 
LVL 5

Expert Comment

by:Kendor
ID: 35099872
TommySzalapski, you are completely right. By posting the code I didn't mean slritmmi to copy my code nor to directly hand it in as is - but rather asked him/her to "have a look" at a possible solution to the problem. And to be honest - I've been away the last 1.5 months and didn't get the chance to answer any questions (+ there are no question I could answer in "my area"... signal processing) - so I hope to get those "least" points to keep my expert status.
Thanks for reminding me anyways.
0
 
LVL 5

Expert Comment

by:Kendor
ID: 35184457
slritmmi is your question resolved? then it would be great from you to close it and assign some points :)
0
 
LVL 101

Expert Comment

by:mlmcc
ID: 36270726
I've requested that this question be deleted for the following reason:

This question has been classified as abandoned and is closed as part of the Cleanup Program. See the recommendation for more details.
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 36270727
http:#a35063128 identified the main critical issues that were causing the errors.
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
This video Micro Tutorial shows how to password-protect PDF files with free software. Many software products can do this, such as Adobe Acrobat (but not Adobe Reader), Nuance PaperPort, and Nuance Power PDF, but they are not free products. This vide…

707 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question