editdis.c

IMPLEMENTATION OF DYNAMIC PROGRAMMING ALGORITHMS FOR EDITDISTANCE PROBLEM IN C

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

main()
{

int i,j,l,k;
char  x[25];
char  y[25];
int  mat[25][25];
for(k=0;k<=25;k++)
	{
   for(l=0;l<=25;l++)
    mat[k][l]=0;
   }
printf("enter the number of character in x\n");
scanf("%d",&i);
printf("enter the string x\n");
scanf("%s",x);
printf("enter the number of character in y\n");
scanf("%d",&j);
printf("enter the string y");
scanf("%s",y);




/* mat=(int *) malloc(sizeof((i+1)*(j+1)*sizeof(int)));*/

 for(l=0;l<=i;l++)
 	{
   mat[l][j]=(i-l)*2;
   }
 for(l=0;l<=j;l++)
 	{
   mat[i][l]=(j-l)*3;
   }

for(l=i-1;l>=0;l--)
	{
   	for(k=j-1;k>=0;k--)
      	{
         	if(*(x+l)==*(y+k))
            	{

               mat[l][k]=mat[l+1][k+1];
               }
            else
            	{
                int ins=3+mat[l][k+1];
                int del=2+mat[(l+1)][k];
                int rep=4+mat[(l+1)][(k+1)];
                if(rep<=ins && rep<=del)
                	mat[l][k]=rep;
                else if(ins<=rep && ins<=del)
                	mat[l][k]=ins;
                else if(del<=rep && del<=ins)
                	mat[l][k]=del;
                }
            }
      };
printf("the edit distance is :%d",mat[0][0]);
getch();
return 0;
}