Java Program for Longest Common Subsequence (LCS) Problem

The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences).

import java.io.*;
import java.util.*;
import java.lang.*;

class LCS1
{
	public static void main(String args[])throws IOException
	{
	int i,j,m,n,c[][],lcs[],ct=1;
	String x,y;
	char b[][];
	c = new int[50][50];
	lcs = new int[10];
	DataInputStream br = new DataInputStream(System.in);
	System.out.print("Enter the Total length of Sequence 1:");
	m = Integer.parseInt(br.readLine());
	System.out.println("Enter the Sequence1:");
	x = br.readLine();
	System.out.print("Enter the Total length of Sequence 2:");
	n = Integer.parseInt(br.readLine());
	System.out.print("Enter the Sequence2:");
	y = br.readLine();
	b = new char[m+1][n+1];
	for(i=0;i<=m;i++)
		c&#91;i&#93;&#91;0&#93;=0;
	for(j=0;j<=n;j++)
		c&#91;0&#93;&#91;j&#93;=0;
	System.out.println(" Table ");
	for(i=0;i<m;i++)
	{
 		for(j=0;j<n;j++)
 		{
  			if(i==0 || j==0)
  			{
  				System.out.print(c&#91;i&#93;&#91;j&#93;);
  				continue;
  			}
  			if((x.charAt(i)==y.charAt(j)))
  			{
   				b&#91;i&#93;&#91;j&#93;='\\';
   				System.out.print(b&#91;i&#93;&#91;j&#93;);
   				c&#91;i&#93;&#91;j&#93;=c&#91;i-1&#93;&#91;j-1&#93;+1;
   				System.out.print(c&#91;i&#93;&#91;j&#93;);
  			}
  			else
  			{
   				if(c&#91;i-1&#93;&#91;j&#93;>=c[i][j-1])
   				{
					b[i][j]='|';
    				System.out.print(b[i][j]);
    				c[i][j]=c[i-1][j];
				    System.out.print(c[i][j]);
   				}
   				else
   				{
    				b[i][j]='-';
    				System.out.print(b[i][j]);
    				c[i][j]=c[i][j-1];
    				System.out.print(c[i][j]);
   				}
  			}
 		}
 		System.out.println();
	}
	i=m-1;
	j=n-1;
	System.out.println(i); 
			System.out.println(j);
	System.out.print("Longest Common Subsequence is :");
	while(i>0 || j>0)
	{
 		if(b[i][j] == '\\')
 		{
 			lcs[ct]=i;
  			ct++;
  			i-=1;
  			j-=1;
 		}
 		else
 		{
  			if(b[i][j]=='|')
  			{
   				i-=1;
   				j=j;
  			}
  			else
  			{
   				i=i;
   				j-=1;
  			}
 		}
	}
	for(i=ct;i>0;i--)
	{
		j=lcs[i];
		System.out.print(x.charAt(j));
	}
	
	}
}

/*
	OUTPUT
Enter the Total length of Sequence 1:9
Enter the Sequence1: president
Enter the Total length of Sequence 2:10
Enter the Sequence2: providence

 Table

  0     0     0     0     0     0     0     0     0     0     0

  0     \1    -1    -1    -1    -1    -1    -1    -1    -1    -1

  0     |1    \2    -2    -2    -2    -2    -2    -2    -2    -2

  0     |1    |2    |2    |2    |2    |2    \3    -3    -3    \3

  0     |1    |2    |2    |2    |2    |2    |3    |3    |3    |3

  0     |1    |2    |2    |2    \3    -3    |3    |3    |3    |3

  0     |1    |2    |2    |2    |3    \4    -4    -4    -4    -4

  0     |1    |2    |2    |2    |3    |4    \5    -5    -5    \5

  0     |1    |2    |2    |2    |3    |4    |5    \6    -6    -6

  0     |1    |2    |2    |2    |3    |4    |5    |6    |6    |6

Longest Common Subsequence is :priden
*/

Leave a Reply

Your email address will not be published. Required fields are marked *