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.  
  81.  
  82.  
  83.  
  84.     int matchCost = f(n-1, m-1) + (A[n] == B[m] ? 0 : 1);
  85.     if(matchCost <= best){
  86.         best = matchCost;
  87.         opt = 0;
  88.     }
  89.  
  90.     int insertCost = f(n, m-1) + 1; // insert B[m] at n + 1
  91.     if(insertCost <= best){
  92.         best = insertCost;
  93.         opt = 1;
  94.     }
  95.  
  96.     int delCost = f(n-1, m) + 1; // delete A[n] at n
  97.     if(delCost <= best){
  98.         best = delCost;
  99.         opt = 2;
  100.     }
  101.  
  102.  
  103.  
  104.    // printf("Traceback %d %d: opt is %d\n",n,m,opt);
  105.  
  106.     if(opt == 0){
  107.         traceBack(n-1, m-1);
  108.         if(A[n] == B[m]){
  109.             // no operation
  110.         } else {
  111.           //  printf("Replace %c with %c at %d\n", A[n], B[m], n);
  112.             ans.push(type(opt, n, B[m]));
  113.         }
  114.     } else if (opt == 1){
  115.         traceBack(n, m-1);
  116.       //  printf("Insert %c at %d\n", B[m], n+1);
  117.         ans.push(type(opt, n+1, B[m]));
  118.     } else if (opt == 2){
  119.         traceBack(n-1, m);
  120.         ans.push(type(opt, n, A[n]));
  121.     }
  122.  
  123. }
  124.  
  125. int main(){
  126.     string a, b;
  127.     //char buff[1000];
  128.     while(cin >> a){
  129.  
  130.         /*a = b = "";
  131.         int index;
  132.         for(index = 0; buff[index]; index++){
  133.             if(buff[index] == ' '){
  134.                 index++;
  135.                 break;
  136.             }
  137.             a.push_back(buff[index]);
  138.         }*/
  139.  
  140.  
  141.         A = " ";
  142.         B = " ";
  143.         if(a == "#") return 0;
  144.         N = a.size();
  145.         A += a;
  146.  
  147.         /*for(index; buff[index]; index++){
  148.             if(buff[index] == '\n'){
  149.                 break;
  150.             }
  151.             b.push_back(buff[index]);
  152.         }*/
  153.         cin >> b;
  154.  
  155.  
  156.         M = b.size();
  157.         B += b;
  158.         arr.assign(N+1, vector<int>(M+1, -1));
  159.         f(N, M);
  160.         traceBack(N, M);
  161.         while(!ans.empty()){
  162.             type t = ans.top();
  163.             ans.pop();
  164.             if(t.opt == 0){
  165.                 printf("C%c%02d", t.val, t.pos);
  166.             } else if (t.opt == 1){
  167.                 printf("I%c%02d", t.val, t.pos);
  168.             } else if (t.opt == 2){
  169.                 printf("Da%02d", t.pos);
  170.             }
  171.         }
  172.         printf("E\n");
  173.     }
  174.  
  175.  
  176.     return 0;
  177. }
  178.  
Success #stdin #stdout 0s 3240KB
comments (?)
stdin
copy 
abcde bcgfe
 adam
asdf 
 
#
stdout
copy 
If05Cg04Da01E
Da04Cf03Is02E
https://ideone.com/DEUg65
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!