c Programming Levenshtein Distance Problem; The problem requires a matrix and th

Question

c Programming Levenshtein Distance Problem; The problem requires a matrix and that is where I'm getting hung up, I'm not real sure on what to use to be able to execute the program properly. The program is supposed to tell the distance between two words when they are entered. This is in c

-declare two strings of maximum size WORD_LEN

-declare an integer square matrix dist with WORD_LEN+1 rows and WORD_LEN+1 columns

-read the two words to compare if the two words are equal display 0 and end the program;

-if any of the two words is empty display the length of the other and end the program;

-Initialize the dist matrix with 0 in every position.

-Initialize the first row and the first column in the matrix:

--for i going from 0 to the length of the first word included set dist[i][0] to i

--for j going from 0 to the length of the second word included  set dist[0][j] to j

-fill the remainder of the matrix (i (row) going from 1 to the length of the first word included, j (column)

- going from 1 to the lengthof the second word included) as follows:

--compute a substitution cost which is 0 if the letter at position i-1 in the first word is equal to the letter at position j-1 in the second word, and 1 otherwise.

-compute a value val which is the minimum of the threefollowing values:

o dist[i-1][j] + 1

o dist[i][j-1] + 1

o dist[i-1][j+1] plus the substitution cost previouslycomputed.set dist[i][j] to val

-Once the matrix is fully computed, the Levenshtein distance is thevalue at the bottom right corner, dist[len1][len2] if len1 is thelength of the first word and len2 the length of the second one.

Explanation / Answer

#include<conio.h>
#include<conio.h>

void main()
{
   int const WORD_LEN=5;

   int dist[6][6],i,j,c=1;

   char s1[WORD_LEN], s2[WORD_LEN];

   printf("Enter 2 Words");
   scanf("%s%s",&s1,&s2);

   if(strcmp(s1,s2)==0)
   {
       printf("0");
       return;
   }

   l1=strlen(s1);
   l2=strlen(s2);

   if(l1==0)
   {
       printf("%d",l2);
       return;
   }
   
   if(l2==0)
   {
       printf("%d",l1);
       return;
   }

   for(i=0;i<6;i++)
   {
       for(j=0;j<6;j++)
       {
           dist[i][j]=0;
       }
   }

   for(i=0;i<6;i++)
   {
       dist[i][0]=i;
   }

   for(j=0;j<6;j++)
   {
       dist[0][j]=j;
   }
  
   for(i=1;i<6;i++)
   {
       for(j=1;j<6;j++)
       {
           dist[i][j]=c;
           c++;
       }
   }

   for(i=1;i<6;i++)
   {
       for(j=1;j<6;j++)
       {
           if(dist[0][i-1]==dist[1][j-1])
           dist[i][j]=0;
           else
           dist[i][j]=1;
       }
   }
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.