/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2009 by Doina Logofatu
************************************************/

import java.io.*;
import java.util.*;

public class P13EditDistance {
  private static final String FileInputName = "edit.in";
  private static final String FileOutputName = "edit.out";
  private int T[][];
  private String x, y;

  P13EditDistance(String x, String y) {
    this.x = x;
    this.y = y;
    this.T = new int[y.length() + 1][x.length() + 1];
  }

  private int getEditDistance() {
    int m = x.length();
    int n = y.length();
    if (m == 0)
      return n;
    if (n == 0)
      return m;

    for (int i = 0; i <= m; i++)
      T[0][i] = i;
    for (int i = 0; i <= n; i++)
      T[i][0] = i;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++) {
        int delta;
        if (x.charAt(j - 1) == y.charAt(i - 1)) {
          delta = 0;
        } else {
          delta=1;
        }
        T[i][j] = Math.min(T[i-1][j-1]+delta, 
                           1+Math.min(T[i-1][j], T[i][j-1]));
      }
    return T[n][m];
  }

  private void writeSolution(PrintStream out, int m, int n, String yaux) {
    boolean flag = false;
    if (m != 0 || n != 0) {
      if (m > 0 && n > 0) {
        if (x.charAt(m - 1) == y.charAt(n - 1)) {
          if (T[n - 1][m - 1] == T[n][m]) {
            flag = true;
            writeSolution(out, m - 1, n - 1, yaux);
          }
        } else {
          if (T[n - 1][m - 1] + 1 == T[n][m]) {
            char[] chArr = yaux.toCharArray();
            chArr[n - 1] = x.charAt(m - 1);
            flag = true;
            String newAux = new String(chArr);
            writeSolution(out, m - 1, n - 1, newAux);
            out.printf("%s T(%d) --> ", newAux, n);
          }
        }
      }

      if (n > 0 && !flag ) {
        if (T[n][m] == T[n - 1][m] + 1) {
          flag = true;
          char chArr[] = new char[yaux.length() - 1];
          if (n > 1) {
            yaux.getChars(0, n - 1, chArr, 0);
          }
          if (n < yaux.length()) {
            yaux.getChars(n, yaux.length(), chArr, n - 1);
          }
          String newAux = new String(chArr);
          writeSolution(out, m, n - 1, newAux);
          out.printf("%s I(%d) --> ", newAux, n);
        }
      }

      if (m > 0 && !flag) {
        if (T[n][m] == T[n][m - 1] + 1) {
          char chArr[] = new char[yaux.length() + 1];
          if (n > 0) {
            yaux.getChars(0, n, chArr, 0);
          }
          chArr[n] = x.charAt(m - 1);
          if (n < yaux.length() - 1) {
            yaux.getChars(n, yaux.length(), chArr, n + 1);
          }
          String newAux = new String(chArr);
          writeSolution(out, m - 1, n, newAux);
          out.printf("%s D(%d) --> ", newAux, n + 1);
        }
      }
    }
  }

  void writeSolution(PrintStream out) {
    out.printf("d(%s, %s) = %d%n", this.x, this.y, this.getEditDistance());
    writeSolution(out, x.length(), y.length(), this.y);
    out.println(this.y);
    out.println("========================");
  }

  public static void main(String[] args) throws IOException {
    Scanner scanner = null;
    PrintStream out = null;
    try {
      scanner = new Scanner(new File(FileInputName));
      out = new PrintStream(new File(FileOutputName));
      while (scanner.hasNext()) {
        String x = scanner.next();
        String y = scanner.next();
        new P13EditDistance(x, y).writeSolution(out);
      }
    } finally {
      if (scanner != null) {
        scanner.close();
      }
      if (out != null) {
        out.close();
      }
    }
  }
}