/************************************************
Algorithmen und Problemloesungen mit C++,
http://www.algorithmen-und-problemloesungen.de
Copyright @2006-2007, Doina Logofatu
************************************************/

#include <string>
#include <fstream>

using namespace std;

short getEditDistance(string x, string y, short T[][101]){
  short m, n, i, j, res;
  m= (short)x.length(); n=(short)y.length();
  if(!m) res = n;
  if(!n) res = m;
  if(m && n){
    for(i=0; i<=m; i++) T[0][i]=i;
    for(i=0; i<=n; i++) T[i][0]=i;
    for(i=1; i<=n; i++)
      for(j=1; j<=m; j++){
        if(x[j-1]==y[i-1]){
          T[i][j]=T[i-1][j-1];
          } 
        else{
          T[i][j]=T[i-1][j-1]+1;
          }
      if(T[i][j]>T[i-1][j]+1) T[i][j]=T[i-1][j]+1; 
      if(T[i][j]>T[i][j-1]+1) T[i][j]=T[i][j-1]+1; 
        }
    res = T[n][m];      
  }
  return res;
}


void writeSolution(int m, int n, short T[][101], 
                   string& x,  string& y, string yaux, 
                   ofstream &out){
  bool flag = false;
  if(m || n){
    if(m>0 && n>0){
      if(x[m-1]==y[n-1]){
        if(T[n-1][m-1]==T[n][m]){
          flag = true;
          writeSolution(m-1, n-1, T, x, y, yaux, out);
          }
        } else{
          if(T[n-1][m-1]+1==T[n][m]){
            yaux.replace(n-1, 1, x.substr(m-1, 1));           
            flag = true;
            writeSolution(m-1, n-1, T, x, y, yaux, out);
            out << yaux << " T(" << n << ") --> ";
            }
          }
      }; 

    if(n>0 && !flag){
      if(T[n][m]==T[n-1][m]+1){
        flag=true;
        yaux.erase(n-1, 1);
        writeSolution( m, n-1, T, x, y, yaux, out );
        out << yaux << " I(" << n << ") --> " ;
        }
      };

    if(m>0 && !flag){
      if(T[n][m]==T[n][m-1]+1){
        yaux.insert(n, x.substr(m-1, 1));
        writeSolution( m-1, n, T, x, y, yaux, out );
        out <<  yaux << " D(" << n+1 << ") --> ";
      }
    };    
  };
}


 int main(){
  string x, y;
  short T[101][101], res;
  ifstream in("edit.in");
  ofstream out("edit.out");
  while(in && !in.eof()){
  if(in >> x >> y){   
    res = getEditDistance(x, y, T);    
    string yaux = y.substr( 0, y.length() );
    out << endl;
    out << "d(" << x << ", " << y << ") = " 
      << res << endl;
    writeSolution((int)x.length(), (int)y.length(), T, 
      x, y, yaux, out);
    out << y << endl << "========================";   
    }
  }
  return 0; 
}