fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main() {
  4.     string s1, s2;
  5.     getline(cin, s1);
  6.     getline(cin, s2);
  7.  
  8.     int m = s1.size();
  9.     int n = s2.size();
  10.     int edit[n+1][m+1];
  11.  
  12.     for (int i = 0; i < n + 1; i++) {
  13.         edit[i][0] = i;
  14.     }
  15.     for (int j = 0; j < m + 1; j++) {
  16.         edit[0][j] = j;
  17.     }
  18.     for (int i = 1; i < n + 1; i++) {
  19.         for (int j = 1; j < m + 1; j++) {
  20.             if (s2[i - 1] == s1[j - 1]) {
  21.                 edit[i][j] = edit[i - 1][j - 1];
  22.             } else {
  23.                 edit[i][j] = 1 + min({edit[i - 1][j], edit[i][j - 1], edit[i - 1][j - 1]});
  24.             }
  25.         }
  26.     }
  27.  
  28.     for (int i = 0; i < n + 1; i++) {
  29.         for (int j = 0; j < m + 1; j++) {
  30.             cout << edit[i][j] << " ";
  31.         }
  32.         cout << endl;
  33.     }
  34.  
  35.     int i = n, j = m;
  36.     while (i > 0 && j > 0) {
  37.         if (s2[i - 1] == s1[j - 1]) {
  38.             i = i - 1;
  39.             j = j - 1;
  40.         } else {
  41.             if (edit[i][j] == 1 + edit[i - 1][j - 1]) {
  42.                 cout << s1[j - 1] << " is replaced by " << s2[i - 1] << endl;
  43.                 i = i - 1;
  44.                 j = j - 1;
  45.             } else if (edit[i][j] == 1 + edit[i - 1][j]) {
  46.                 cout << s2[i - 1] << " is inserted" << endl;
  47.                 i = i - 1;
  48.             } else {
  49.                 cout << s1[j - 1] << " is deleted" << endl;
  50.                 j = j - 1;
  51.             }
  52.         }
  53.     }
  54.     while (j > 0) {
  55.         cout << s1[j - 1] << " is deleted" << endl;
  56.         j = j - 1;
  57.     }
  58.     while (i > 0) {
  59.         cout << s2[i - 1] << " is inserted" << endl;
  60.         i = i - 1;
  61.     }
  62. }
  63.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
abcdef
ayced
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
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/LBnv1I
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!