fork download
copy 
  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.     int m = s1.size();
  10.     int n = s2.size();
  11.     int EDIT[n+1][m+1];
  12.  
  13.     for(int i = 0; i < m+1; i++)
  14.     {
  15.         EDIT[0][i] = i;
  16.     }
  17.     for(int i = 0; i < n+1; i++)
  18.     {
  19.         EDIT[i][0] = i;
  20.     }
  21.  
  22.  
  23.     for(int i = 1; i < n+1; i++)
  24.     {
  25.         for(int j = 1; j < m+1; j++)
  26.         {
  27.             if(s1[j-1] == s2[i-1])
  28.             {
  29.                 EDIT[i][j] = EDIT[i-1][j-1];
  30.             }
  31.             else
  32.             {
  33.                 EDIT[i][j] = 1 + min({EDIT[i-1][j-1], EDIT[i-1][j], EDIT[i][j-1]});
  34.             }
  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.     int i = n, j = m;
  49.     while( i > 0)
  50.     {
  51.         if(s1[j-1] == s2[i-1])
  52.         {
  53.             i = i-1;
  54.             j = j-1;
  55.         }
  56.         else
  57.         {
  58.             if(EDIT[i][j] ==  1+ EDIT[i-1][j])
  59.             {
  60.                 cout<<s1[j-1]<<" is inserted"<<endl;
  61.                 i = i-1;
  62.             }
  63.             else if(EDIT[i][j] == 1+EDIT[i][j-1])
  64.             {
  65.                 cout<<s1[j-1]<<" is deleted"<<endl;
  66.                 j = j-1;
  67.             }
  68.             else
  69.             {
  70.                 cout<<s1[j-1]<<" is replaced to "<<s2[i-1]<<endl;
  71.                 i = i-1;
  72.                 j = j-1;
  73.             }
  74.         }
  75.     }
  76. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/74Ynzr
language:
C++ (gcc 8.3)
created:
4 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!