Learn to build secure applications from the mindset of the hacker and avoid being exploited.

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?

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

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialBTW, 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.

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

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.

Thanks for reminding me anyways.

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

http:#a35063128 identified the main critical issues that were causing the errors.

Algorithms

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

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