fork download
copy 
  1. #include <string.h>
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4.  
  5. int lcs(const char* s1, const char* s2)
  6. {
  7.   size_t l1 = strlen(s1), l2 = strlen(s2);
  8.   size_t sz = (l1 + 1) * (l2 + 1) * sizeof(size_t);
  9.   size_t w = l2 + 1;
  10.   size_t* dpt;
  11.   size_t i1, i2;
  12.  
  13.   if (sz / (l1 + 1) / (l2 + 1) != sizeof(size_t) ||
  14.       (dpt = malloc(sz)) == NULL)
  15.   {
  16.     printf("Not enough memory\n");
  17.     return EXIT_FAILURE;
  18.   }
  19.  
  20.   for (i1 = 0; i1 <= l1; i1++)
  21.     dpt[w * i1 + 0] = 0;
  22.   for (i2 = 0; i2 <= l2; i2++)
  23.     dpt[w * 0 + i2] = 0;
  24.  
  25.   for (i1 = 1; i1 <= l1; i1++)
  26.     for (i2 = 1; i2 <= l2; i2++)
  27.     {
  28.       if (s1[l1 - i1] == s2[l2 - i2])
  29.       {
  30.         dpt[w * i1 + i2] = dpt[w * (i1 - 1) + (i2 - 1)] + 1;
  31.       }
  32.       else if (dpt[w * (i1 - 1) + i2] > dpt[w * i1 + (i2 - 1)])
  33.       {
  34.         dpt[w * i1 + i2] = dpt[w * (i1 - 1) + i2];
  35.       }
  36.       else
  37.       {
  38.         dpt[w * i1 + i2] = dpt[w * i1 + (i2 - 1)];
  39.       }
  40.     }
  41.  
  42.   i1 = l1; i2 = l2;
  43.   for (;;)
  44.   {
  45.     if ((i1 > 0) && (i2 > 0) && (s1[l1 - i1] == s2[l2 - i2]))
  46.     {
  47.       printf("%c", s1[l1 - i1]);
  48.       i1--; i2--; continue;
  49.     }
  50.     else
  51.     {
  52.       if (i1 > 0 &&
  53.           (i2 == 0 || dpt[w * (i1 - 1) + i2] >= dpt[w * i1 + (i2 - 1)]))
  54.       {
  55.         printf("-%c", s1[l1 - i1]);
  56.         i1--; continue;
  57.       }
  58.       else if (i2 > 0 &&
  59.                (i1 == 0 || dpt[w * (i1 - 1) + i2] < dpt[w * i1 + (i2 - 1)]))
  60.       {
  61.         printf("+%c", s2[l2 - i2]);
  62.         i2--; continue;
  63.       }
  64.     }
  65.  
  66.     break;
  67.   }
  68.   printf("\n");
  69.  
  70.   free(dpt);
  71.   return EXIT_SUCCESS;
  72. }
  73.  
  74. int main(int argc, char** argv)
  75. {
  76.   const char *s1, *s2;
  77.   if (argc == 3)
  78.   {
  79.     s1 = argv[1]; s2 = argv[2];
  80.   }
  81.   else
  82.   {
  83.     printf("Usage:\n  lcs-diff.exe <string1> <string2>\n\n");
  84.     s1 = "I ate apple on yesterday"; s2 = "I eat apple yesterday";
  85.     printf("Sample comparison:\n\n  \"%s\" vs \"%s\":\n\n", s1, s2);
  86.   }
  87.  
  88.   return lcs(s1, s2);
  89. }
  90.  
Success #stdin #stdout 0s 1964KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Usage:
  lcs-diff.exe <string1> <string2>

Sample comparison:

  "I ate apple on yesterday" vs "I eat apple yesterday":

I +eat-e apple -o-n- yesterday
https://ideone.com/EP19R6
language:
C (gcc 8.3)
created:
11 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!