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