C Program to find Least Common Subsequence between two strings
Note: The subsequence in the output is in reverse order.
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
int main()
{
int i,j;
printf("\t\tLONGEST COMMON SUBSEQUENCE\n");
char a[] = "abcbdab";
char b[] = "bdcaba";
int la = strlen(a);
int lb = strlen(b);
int C[la+1][lb+1];
char dir[la+1][lb+1];
for(i=0;i<=la;i++)
C[i][0] = 0;
for(i=0;i<=lb;i++)
C[0][i] = 0;
for(i=1;i<=la;i++)
{
for(j=1;j<=lb;j++)
{
if(a[i-1]==b[j-1])
{
C[i][j] = C[i-1][j-1] + 1 ;
dir[i][j] = 'd';
}
else if(C[i-1][j] >= C[i][j-1])
{
C[i][j] = C[i-1][j];
dir[i][j] = 'u';
}
else
{
C[i][j] = C[i][j-1];
dir[i][j] = 'l';
}
}
}
for(i=0;i<la;i++)
printf(" %c ",b[i]);
for(i=1;i<=la;i++)
{
printf("\n");
printf(" %c ",a[i-1]);
for(j=1;j<=lb;j++)
{
printf(" %d %c ",C[i][j],dir[i][j]);
}
}
printf("\n\tCOST = %d\n",C[la][lb]);
i = la ; j = lb ;
while((i!=0)||(j!=0))
{
if(dir[i][j]=='d')
{
printf(" %c ",a[i-1]);
i--; j--;
}
else if(dir[i][j]=='l')
j--;
else i--;
}
return 0;
}
