fork download
copy 
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  6. /*
  7.  *      Returns and memoizes the edit distance from a + i to b + j
  8.  */
  9. int dist_(int memo[12][12], const char *a, const char *b, int i, int j)
  10. {
  11.     int ans = memo[i][j];
  12.  
  13.     if (ans < 0) {
  14.         if (a[i] && b[j]) {
  15.             if (a[i] == b[j]) {
  16.                 ans = dist_(memo, a, b, i + 1, j + 1);
  17.             } else {
  18.                 int ans1 = dist_(memo, a, b, i + 1, j + 0);
  19.                 int ans2 = dist_(memo, a, b, i + 0, j + 1);
  20.                 int ans3 = dist_(memo, a, b, i + 1, j + 1);
  21.  
  22.                 if (ans3 < ans1 && ans3 < ans2) {
  23.                     ans = ans3 + 1;
  24.                 } else {
  25.                     if (ans1 < ans2) {
  26.                         ans = ans1 + 1;
  27.                     } else {
  28.                         ans = ans2 + 1;
  29.                     }
  30.                 }
  31.             }
  32.         } else {
  33.             ans = strlen(a + i)
  34.                 + strlen(b + j);
  35.         }
  36.  
  37.         memo[i][j] = ans;
  38.     }
  39.  
  40.     return ans;
  41. }
  42.  
  43. /*
  44.  *      Font end to recursive distance function
  45.  */
  46. int distance(const char *a, const char *b)
  47. {
  48.     int memo[12][12];
  49.  
  50.     memset(memo, -1, sizeof(memo));
  51.  
  52.     return dist_(memo, a, b, 0, 0);
  53. }
  54.  
  55.  
  56.  
  57. /*
  58.  *      Driver code for some simple tests
  59.  */
  60. int failed(const char *a, const char *b, int expected)
  61. {
  62.     int res = distance(a, b);
  63.  
  64.     printf("dist('%s', '%s') == %d", a, b, res);
  65.  
  66.     if (res == expected) {
  67.         printf(" ok\n");
  68.  
  69.         return 0;
  70.     }
  71.  
  72.     printf(", but expected %d\n", expected);
  73.  
  74.     return 1;
  75. }
  76.  
  77. int main(void)
  78. {
  79.     int fail = failed("editing", "distance", 5)
  80.              + failed("distance", "editing", 5)
  81.              + failed("kitten", "sitting", 3)
  82.              + failed("sitting", "kitten", 3)
  83.              + failed("crimson", "crimson", 0)
  84.              + failed("fish", "fishy", 1);
  85.  
  86.     printf("\n%d failed tests.\n", fail);
  87.  
  88.     return 0;
  89. }
  90.  
Success #stdin #stdout 0s 4688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
dist('editing', 'distance') == 5 ok
dist('distance', 'editing') == 5 ok
dist('kitten', 'sitting') == 3 ok
dist('sitting', 'kitten') == 3 ok
dist('crimson', 'crimson') == 0 ok
dist('fish', 'fishy') == 1 ok

0 failed tests.
https://ideone.com/JKaFEB
language:
C (gcc 8.3)
created:
4 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!