Least common subsequence

Input	Two Strings (tested for 20 character string)
Output	Longest Common Subsequence
Complexity	O(mn)

LCS(X, Y)
[length[X] counts the length of String X. b and c matrix is maintained in which information about longest common subsequence is stored using dynamic programming.]

1 m ← length[X]
2 n ← length[Y]
3 for i ← 1 to m
4 	do c[i, 0] ← 0
5 for j ← 0 to n
6 	do c[0, j] ← 0
7 for i ← 1 to m
8 	do for j ← 1 to n
9 		do if xi = yj
10 			then c[i, j] ← c[i - 1, j - 1] + 1
11 				b[i, j] ← “^"
12	 	else if c[i - 1, j] ≥ c[i, j - 1]
13 			then c[i, j] ← c[i - 1, j]
14 				b[i, j] ← "↑"
15 		else c[i, j] ← c[i, j - 1]
16 				b[i, j] ← “←”
17 return c and b

//WAP to find Longest Common Subsequence

#include<stdio.h>
#include<conio.h>
#include<string.h>

void lcs(char[],char[]);
void showlcs(char[][20],char[],int,int);

int main()
{
	 int i,j;
	 char a[20],b[20];
	 printf("Enter 1st sequence:");
	 gets(a);
	 printf("Enter 2nd sequence:");
	 gets(b);
	 printf("\nLCS is :");
	 lcs(a,b);
	 getch();
}

void lcs(char x[],char y[])
{
	 int m,n,i,j,c[20][20];
	 char b[20][20];
	 m=strlen(x);//find length of 1st sequence
	 n=strlen(y);//find lenght of 2nd sequence
	 for(i=0;i<=m;i++)
	  c[i][0]=0;//set first column to zero
	 for(i=1;i<=n;i++)
	  c[0][i]=0;//set first row to zero
	 for(i=1;i<=m;i++)
	 {
	 for(j=1;j<=n;j++)
	 {
		if(x[i-1]==y[j-1])
		{
		c[i][j]=c[i-1][j-1]+1;
		b[i][j]='\ ';//'\ ' is north-west direction
		}
		else if(c[i-1][j]>=c[i][j-1])
		{
		c[i][j]=c[i-1][j];
		b[i][j]='^';//'^' is north direction
		}
		else
		{
		c[i][j]=c[i][j-1];
		b[i][j]='>-';//'<-' is west direction
		}
	}
	}
	showlcs(b,x,m,n);//print the result
}

void showlcs(char b[][20],char x[],int i,int j)
{
	 if(i==0 || j==0)//if both seq. has zero length
	  return;       //return null
	 if(b[i][j]=='\ ')
	 {
	 showlcs(b,x,i-1,j-1);
	 printf(" %c",x[i-1]);
	 }
	 else if(b[i][j]=='^')
	 showlcs(b,x,i-1,j);
	 else
	 showlcs(b,x,i,j-1);
}

import java.io.*;
import java.lang.*;
class lcs
{
      public static void main(String args[]) throws IOException
      {
            int i,j,k,m,n;
            BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
            System.out.println("Enter the  1st string ");
            String x=br.readLine();
            System.out.println("Enter the  2nd string ");
            String y=br.readLine();
            m=x.length();
            n=y.length();
            int l[][]=new int[m+1][n+1];
		for(i=0;i<=m;i++)
			l[i][0]=0;
	      for (j=1;j<=n;j++)
			l[0][j]=0;
            for (i=1;i<=m;i++)
            {		
                  for (j=1;j<=n;j++)
			{	
                        if (x.charAt(i-1)==y.charAt(j-1))
		      		l[i][j]=l[i-1][j-1] + 1;
				else
				if((l[i-1][j]>l[i][j-1]))
                       		l[i][j]=l[i-1][j]; 
                        else
                       		l[i][j]=l[i][j-1];
                 }
            }
 	      char common[]=new char[l[m][n]];
            for (k=0,i=m,j=n; i>0 && j>0;)
	      {
			if (x.charAt(i-1)==y.charAt(j-1))
			{
				common[k++] = x.charAt(i-1);
				i--;
                        j--;
			}
			else
			if(l[i-1][j] >= l[i][j-1]) 
	                i--;
	            else
      	          j--;
	     }
	     String common1 =  new String(common);
           StringBuffer common2 =  new StringBuffer(common1);
           System.out.println("the longest common subsequence is "+common2.reverse());
      }
}