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.  
  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; //insert
  18.     }
  19.     for(int j = 0; j < m+1; j++)
  20.     {
  21.         edit[0][j] = j; // delete
  22.     }
  23.  
  24.     for(int i = 1; i < n+1; i++)
  25.     {
  26.         for(int j = 1; j < m+1; j++)
  27.         {
  28.             if(s2[i-1] == s1[j-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.  
  50.     int i = n, j = m;
  51.     while(i > 0)
  52.     {
  53.         if(s2[i-1] == s1[j-1])
  54.         {
  55.             i = i-1;
  56.             j = j-1;
  57.         }
  58.         else
  59.         {
  60.             if(edit[i][j] ==  1+ edit[i-1][j-1])
  61.             {
  62.                 cout<<s1[j-1]<<" is replaced by "<<s2[i-1]<<endl;
  63.                 i = i-1;
  64.                 j = j-1;
  65.             }
  66.             else if(edit[i][j] == 1 + edit[i-1][j])
  67.             {
  68.                 cout<<s2[i-1]<<" is inserted"<<endl;
  69.                 i = i-1;
  70.             }
  71.             else
  72.             {
  73.                 cout<<s1[j-1]<<" is deleted"<<endl;
  74.                 j = j - 1;
  75.             }
  76.         }
  77.     }
  78.  
  79.  
  80.  
  81. }
  82.  
Success #stdin #stdout 0.01s 5268KB
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/vp37K9
language:
C++ (gcc 8.3)
created:
2 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!