14 April, 2012

lcs


#include<stdio.h>
#include<string.h>
char **b;
void print(char *x,int m,int n)
{
        if(m==0||n==0)
        return;
        if(b[m][n]=='!')
        {
                print(x,m-1,n-1);
                printf("%c",x[m-1]);
        }
        else if(b[m][n]=='@')
        print(x,m-1,n);
        else
        print(x,m,n-1);
}
void lcs(char *x,char *y)
{
        int m,n,**c,i,j;
        m=strlen(x);
        n=strlen(y);
        c=(int **)malloc((m+1)*sizeof(int *));
        for(i=0;i<m+1;i++)
        c[i]=(int *)malloc((n+1)*sizeof(int));
        b=(char **)malloc((m+1)*sizeof(char *));
        for(i=0;i<m+1;i++)
        b[i]=(char *)malloc((n+1)*sizeof(char));
        for(i=0;i<m;i++)
        {
                c[i][0]=0;
                b[i][0]=0;
        }
        for(i=0;i<n;i++)
        {
                c[0][i]=0;
                b[0][i]=0;
        }
        for(i=0;i<m;i++)
        {
                for(j=0;j<n;j++)
                {
                        if(x[i]==y[j])
                        {
                                c[i+1][j+1]=c[i][j]+1;
                                b[i+1][j+1]='!';
                        }
                        else if(c[i][j+1]>=c[i+1][j])
                        {
                                c[i+1][j+1]=c[i][j+1];
                                b[i+1][j+1]='@';
                        }
                        else
                        {
                                c[i+1][j+1]=c[i+1][j];
                                b[i+1][j+1]='#';
                        }
                }
        }
        printf("\nLength of LCS=%d\nSubsequence is\n",c[m][n]);
        print(x,m,n);
        printf("\n");
}

int main()
{
        int i,j;
        char x[50],y[50];
        system("clear");
        printf("Enter first sequence\n");
        scanf("%s",&x);
        printf("Enter second sequence\n");
        scanf("%s",&y);
        lcs(x,y);
}

No comments:

Post a Comment