fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.     string s1, s2;
  7.     getline(cin, s1);
  8.     getline(cin, s2);
  9.  
  10.     int m = s1.size();
  11.     int n = s2.size();
  12.  
  13.     int edit[n+1][m+1];
  14.  
  15.     for(int i = 0; i < n+1; i++)
  16.     {
  17.         edit[i][0] = i;
  18.     }
  19.     for(int j = 0; j < m+1; j++)
  20.     {
  21.         edit[0][j] = j;
  22.     }
  23.  
  24.     for(int i = 1; i < n+1; i++)
  25.     {
  26.         for(int j = 1; j < m+1; j++)
  27.         {
  28.             if(s1[j-1] == s2[i-1])
  29.             {
  30.                 edit[i][j] = edit[i-1][j-1];
  31.             }
  32.             else
  33.             {
  34.                 edit[i][j] = 1 + min({edit[i-1][j], edit[i][j-1], edit[i-1][j-1]});
  35.             }
  36.         }
  37.     }
  38.  
  39.     for(int i = 0; i < n+1; i++)
  40.     {
  41.         for(int j = 0; j < m+1; j++)
  42.         {
  43.             cout<<edit[i][j]<<" ";
  44.         }
  45.         cout<<endl;
  46.     }
  47.  
  48.  
  49.     int i = n, j = m;
  50.     while( i > 0)
  51.     {
  52.         if(s2[i-1] == s1[j-1])
  53.         {
  54.             i--;
  55.             j--;
  56.         }
  57.         else
  58.         {
  59.             if(edit[i][j] == 1 + edit[i-1][j-1])
  60.             {
  61.                 cout<<s1[j-1]<<" is replaced by "<<s2[i-1]<<endl;
  62.                 i--;
  63.                 j--;
  64.             }
  65.             else if( edit[i][j] ==  1 + edit[i][j-1])
  66.             {
  67.                 cout<<s1[j-1]<<" is deleted"<<endl;
  68.                 j--;
  69.             }
  70.             else
  71.             {
  72.                 cout<<s2[i-1]<<" is inserted"<<endl;
  73.                 i--;
  74.             }
  75.  
  76.         }
  77.     }
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85. }
  86.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin 
kitten                                                                      sitting
stdout 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
https://ideone.com/do8I6g
language:
C++ (gcc 8.3)
created:
6 days 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!