fork download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4.  
  5. // Change these strings to test the program
  6. #define STRING_X "SUNDAY"
  7. #define STRING_Y "SATURDAY"
  8.  
  9. #define SENTINEL (-1)
  10. #define INSERT_COST (1)
  11. #define DELETE_COST (1)
  12. #define REPLACE_COST (1)
  13.  
  14. inline
  15. int min(int a, int b) {
  16.    return a < b ? a : b;
  17. }
  18.  
  19. // Returns Minimum among a, b, c
  20. int Minimum(int a, int b, int c)
  21. {
  22.     return min(min(a, b), c);
  23. }
  24.  
  25. // Strings of size m and n are passed.
  26. // Construct the Table for X[0...m, m+1], Y[0...n, n+1]
  27. int EditDistanceDP(char X[], char Y[])
  28. {
  29.     // Cost of alignment
  30.     int cost = 0;
  31.     int leftCell, topCell, cornerCell;
  32.  
  33.     int m = strlen(X)+1;
  34.     int n = strlen(Y)+1;
  35.  
  36.     // T[m][n]
  37.     int *T = (int *)malloc(m * n * sizeof(int));
  38.  
  39.     // Initialize table
  40.     for(int i = 0; i < m; i++)
  41.         for(int j = 0; j < n; j++)
  42.             *(T + i * n + j) = SENTINEL;
  43.  
  44.     // Set up base cases
  45.     // T[i][0] = i
  46.     for(int i = 0; i < m; i++)
  47.         *(T + i * n) = i;
  48.  
  49.     // T[0][j] = j
  50.     for(int j = 0; j < n; j++)
  51.         *(T + j) = j;
  52.  
  53.     // Build the T in top-down fashion
  54.     for(int i = 1; i < m; i++)
  55.     {
  56.         for(int j = 1; j < n; j++)
  57.         {
  58.             // T[i][j-1]
  59.             leftCell = *(T + i*n + j-1);
  60.             leftCell += DELETE_COST; // deletion
  61.  
  62.             // T[i-1][j]
  63.             topCell = *(T + (i-1)*n + j);
  64.             topCell += INSERT_COST; // insertion
  65.  
  66.             // Top-left (corner) cell
  67.             // T[i-1][j-1]
  68.             cornerCell = *(T + (i-1)*n + (j-1) );
  69.  
  70.             // edit[(i-1), (j-1)] = 0 if X[i] == Y[j], 1 otherwise
  71.             cornerCell += REPLACE_COST * (X[i-1] != Y[j-1]); // may be replace
  72.  
  73.             // Minimum cost of current cell
  74.             // Fill in the next cell T[i][j]
  75.             *(T + (i)*n + (j)) = Minimum(leftCell, topCell, cornerCell);
  76.         }
  77.     }
  78.  
  79.     // Cost is in the cell T[m][n]
  80.     cost = *(T + m*n - 1);
  81.     free(T);
  82.     return cost;
  83. }
  84.  
  85. // Recursive implementation
  86. int EditDistanceRecursion( char *X, char *Y, int m, int n )
  87. {
  88.     // Base cases
  89.     if( m == 0 && n == 0 )
  90.         return 0;
  91.  
  92.     if( m == 0 )
  93.         return n;
  94.  
  95.     if( n == 0 )
  96.         return m;
  97.  
  98.     // Recurse
  99.     int left = EditDistanceRecursion(X, Y, m-1, n) + 1;
  100.     int right = EditDistanceRecursion(X, Y, m, n-1) + 1;
  101.     int corner = EditDistanceRecursion(X, Y, m-1, n-1) + (X[m-1] != Y[n-1]);
  102.  
  103.     return Minimum(left, right, corner);
  104. }
  105.  
  106. int main()
  107. {
  108.     char X[] = STRING_X; // vertical
  109.     char Y[] = STRING_Y; // horizontal
  110.  
  111.     printf("Minimum edits required to convert %s into %s is %d\n",
  112.            X, Y, EditDistanceDP(X, Y) );
  113.     printf("Minimum edits required to convert %s into %s is %d by recursion\n",
  114.            X, Y, EditDistanceRecursion(X, Y, strlen(X), strlen(Y)));
  115.  
  116.     return 0;
  117. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Minimum edits required to convert SUNDAY into SATURDAY is 3
Minimum edits required to convert SUNDAY into SATURDAY is 3 by recursion
https://ideone.com/ebNWUz
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!