fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. string A,B;
  6.  
  7. class type{
  8. public:
  9.     int opt, pos;
  10.     char val;
  11.     type(){}
  12.     type(int OPT, int POS, char VAL) : opt(OPT), pos(POS), val(VAL){}
  13. };
  14.  
  15. int N, M;
  16. vector<vector<int>> arr;
  17. stack<type> ans;
  18.  
  19. int f(int n, int m){
  20.     if(arr[n][m] != -1){
  21.         return arr[n][m];
  22.     }
  23.  
  24.     if(!n && !m){
  25.         return 0;
  26.     }
  27.     if(!n){ // insert B[m] at n+1
  28.            // printf("%d %d: %d = %d\n", n,m, 1, f(n, m-1) + 1);
  29.         return arr[n][m] = f(n, m-1) + 1;
  30.     }
  31.     if(!m){ // delete A[n] at n
  32.       //  printf("%d %d: %d = %d\n", n,m, 2, f(n-1, m) + 1);
  33.         return arr[n][m] = f(n-1, m) + 1;
  34.     }
  35.  
  36.     int best = max(n, m);
  37.     int opt = -1;
  38.     int matchCost = f(n-1, m-1) + (A[n] == B[m] ? 0 : 1);
  39.     if(matchCost <= best){
  40.         best = matchCost;
  41.         opt = 0;
  42.     }
  43.    // printf("matchCost for %d %d is %d\n", n, m , matchCost);
  44.     int insertCost = f(n, m-1) + 1; // insert B[m] at n+1
  45.     if(insertCost <= best){
  46.         best = insertCost;
  47.         opt = 1;
  48.     }
  49.   //  printf("insertCost for %d %d is %d\n", n,m,insertCost);
  50.     int delCost = f(n-1, m) + 1; // delete A[n] at n
  51.     if(delCost <= best){
  52.         best = delCost;
  53.         opt = 2;
  54.     }
  55.    // printf("delCost for %d %d is %d\n", n,m,delCost);
  56.  
  57.  
  58.   //  printf("Best cost for %d %d is %d\n", n,m,  best);
  59.     return arr[n][m] = best;
  60. }
  61.  
  62. void traceBack(int n, int m){
  63.    // printf("Traceback %d %d\n",n,m);
  64.     if(!n && !m){
  65.         return;
  66.     }
  67.     if(!n){ // insert B[m] at n + 1
  68.         traceBack(n, m-1);
  69.         ans.push(type(1, n+1, B[m]));
  70.         return;
  71.     }
  72.     if(!m){ // delete A[n] at n
  73.         traceBack(n-1, m);
  74.         ans.push(type(2, n, A[n]));
  75.         return;
  76.     }
  77.  
  78.     int best = max(n, m);
  79.     int opt = -1;
  80.     int matchCost = f(n-1, m-1) + (A[n] == B[m] ? 0 : 1);
  81.     if(matchCost <= best){
  82.         best = matchCost;
  83.         opt = 0;
  84.     }
  85.     int insertCost = f(n, m-1) + 1; // insert B[m] at n + 1
  86.     if(insertCost <= best){
  87.         best = insertCost;
  88.         opt = 1;
  89.     }
  90.     int delCost = f(n-1, m) + 1; // delete A[n] at n
  91.     if(delCost <= best){
  92.         best = delCost;
  93.         opt = 2;
  94.     }
  95.  
  96.    // printf("Traceback %d %d: opt is %d\n",n,m,opt);
  97.  
  98.     if(opt == 0){
  99.         traceBack(n-1, m-1);
  100.         if(A[n] == B[m]){
  101.             // no operation
  102.         } else {
  103.           //  printf("Replace %c with %c at %d\n", A[n], B[m], n);
  104.             ans.push(type(opt, n, B[m]));
  105.         }
  106.     } else if (opt == 1){
  107.         traceBack(n, m-1);
  108.       //  printf("Insert %c at %d\n", B[m], n+1);
  109.         ans.push(type(opt, n+1, B[m]));
  110.     } else if (opt == 2){
  111.         traceBack(n-1, m);
  112.         ans.push(type(opt, n, A[n]));
  113.     }
  114.  
  115. }
  116.  
  117. int main(){
  118.     string a, b;
  119.     char buff[1000];
  120.     while(fgets(buff, 10000, stdin)!=NULL){
  121.  
  122.         a = b = "";
  123.         int index;
  124.         for(index = 0; buff[index]; index++){
  125.             if(buff[index] == ' '){
  126.                 index++;
  127.                 break;
  128.             }
  129.             a.push_back(buff[index]);
  130.         }
  131.  
  132.  
  133.         A = " ";
  134.         B = " ";
  135.         if(a == "#") return 0;
  136.         N = a.size();
  137.         A += a;
  138.  
  139.         for(index; buff[index]; index++){
  140.             if(buff[index] == '\n'){
  141.                 break;
  142.             }
  143.             b.push_back(buff[index]);
  144.         }
  145.  
  146.  
  147.  
  148.         M = b.size();
  149.         B += b;
  150.         arr.assign(N+1, vector<int>(M+1, -1));
  151.         f(N, M);
  152.         traceBack(N, M);
  153.         while(!ans.empty()){
  154.             type t = ans.top();
  155.             ans.pop();
  156.             if(t.opt == 0){
  157.                 printf("C%c%02d", t.val, t.pos);
  158.             } else if (t.opt == 1){
  159.                 printf("I%c%02d", t.val, t.pos);
  160.             } else if (t.opt == 2){
  161.                 printf("Da%02d", t.pos);
  162.             }
  163.         }
  164.         printf("E\n");
  165.     }
  166.  
  167.  
  168.     return 0;
  169. }
  170.  
Success #stdin #stdout 0s 3284KB
comments (?)
stdin
copy 
abcde bcgfe
#
stdout
copy 
If05Cg04Da01E
Da02Da01E
https://ideone.com/sGgOsw
language:
C++14 (gcc 8.3)
created:
9 years 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!