Wednesday 27 August 2014

Longest Common Subsequence in Java using Dynamic Programming

In case you find some error feel free to comment.


/*
I haven`t refactored the code for words with spaces
This Program uses Dynamic Programming Approach
*/
class LCS
{

   public static void main(String args[])
   {
      System.out.print("Enter First String : ");
 String x=System.console().readLine();
 System.out.print("Enter Second String : ");
 String y=System.console().readLine();

 char[]xArray=x.toCharArray();
 char[]yArray=y.toCharArray();

 int xSize=xArray.length;
 int ySize=yArray.length;

 int lcs[][]=new int[xSize+1][ySize+1];
 String marks[][]=new String[xSize][ySize];

 for(int j=0;j<=ySize;j++)
 {
    lcs[0][j]=0;
 }
 for(int i=0;i<=xSize;i++)
 {
   lcs[i][0]=0;
 }
 for(int i=1;i<=xSize;i++)
 {
     for(int j=1;j<=ySize;j++)
 {
    if(xArray[i-1]==yArray[j-1])
{
  lcs[i][j]=lcs[i-1][j-1]+1;
  marks[i-1][j-1]="D";
}
else if(lcs[i][j-1] >= lcs[i-1][j])
{
  lcs[i][j]=lcs[i][j-1];
  marks[i-1][j-1]="L";
}
else
{
  lcs[i][j]=lcs[i-1][j];
  marks[i-1][j-1]="U";
}
 }
 }
 /*
 System.out.println("\nLCS Matrix is : ");

 System.out.println();
 for(int i=0;i<=xSize;i++)
 {
 
   for(int j=0;j<=ySize;j++)
{
 System.out.print(lcs[i][j]+"\t");
}
System.out.println();
 }
 */

/* System.out.println("Marks Matrix is :");
 for(int i=0;i<xSize;i++)
 {
   for(int j=0;j<ySize;j++)
{
 System.out.print(marks[i][j]+"  ");
}
System.out.println();
 }
 */
 int i=xSize-1;
      int j=ySize-1;
      System.out.println("----------------------------------------------");
      int counter=lcs[xSize][ySize];
 System.out.println("Longest Common SubSequence Length is :"+counter);
 System.out.println("----------------------------------------------");
      char[]lcsArray=new char[counter];
      int fill=0;
      int seen=0;
 while(seen != counter)
 {  
     // System.out.print(marks[i][j]+"  ");
      if(marks[i][j].equals("U"))
  {
     i=i-1;
  }
  else if(marks[i][j].equals("L"))
  {
     j=j-1;
  }
  else
  {
      lcsArray[fill]=xArray[i];
  fill++;
      i=i-1;
  j=j-1;
 seen++;
  }
 
 }
 System.out.print("Longest Common SubSequence is : ");
 int lcsLength=lcsArray.length;
 for(int k=0;k<lcsLength;k++)
 {
    System.out.print(lcsArray[lcsLength-k-1]);
 }
 System.out.println();
 
   }

}

No comments:

Post a Comment