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.  
  12.     int EDIT[n+1][m+1];
  13.  
  14.     for(int i = 0; i < m+1; i++)
  15.     {
  16.         EDIT[0][i] = i;
  17.     }
  18.     for(int i = 0; i< n+1; i++)
  19.     {
  20.         EDIT[i][0] = i;
  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], EDIT[i][j-1], EDIT[i-1][j-1]});
  34.             }
  35.         }
  36.     }
  37.  
  38.     for(int i = 0; i < n+1; i++)
  39.     {
  40.         for(int j = 0; j < m+1; j++)
  41.         {
  42.             cout<<EDIT[i][j]<<" ";
  43.         }
  44.         cout<<endl;
  45.     }
  46.  
  47.     int i = n, j = m;
  48.     while(i > 0)
  49.     {
  50.         //cout<<i<<" "<<j<<endl;
  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-1])
  59.             {
  60.                 cout<<s1[j-1]<<" is replaced by "<<s2[i-1]<<endl;
  61.                 i = i-1;
  62.                 j = j-1;
  63.             }
  64.             else if(EDIT[i][j] == 1 + EDIT[i-1][j])
  65.             {
  66.                 cout<<s1[j-1]<<" is inserted"<<endl;
  67.                 i = i-1;
  68.             }
  69.             else
  70.             {
  71.                 cout<<s1[j-1]<<" is deleted"<<endl;
  72.                 j = j-1;
  73.             }
  74.         }
  75.     }
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84. }
  85.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
abcdef
ayced
stdout
copy 
0 1 2 3 4 5 6 
1 0 1 2 3 4 5 
2 1 1 2 3 4 5 
3 2 2 1 2 3 4 
4 3 3 2 2 2 3 
5 4 4 3 2 3 3 
f is replaced by d
d is deleted
b is replaced by y
https://ideone.com/OTZwmb
language:
C++ (gcc 8.3)
created:
12 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!