1.


/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 164 - String Computer
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=100
*
* @author Dennis Wilfert
* @version 1.0, 11/30/2009
*
* Status : Accepted
* Runtime: 1.012
*/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.StringTokenizer;

class Main {

static String s0;
static String s1;
static int[][] d = new int[22][22];

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintStream out = new PrintStream(new BufferedOutputStream(System.out));
StringTokenizer token;
String tmp;

int i, j, l1, l2;
// x- und y-Achse aufsteigen nummerieren
for (i = 1; i < 22; i++) {
d[i][0] = i;
d[0][i] = i;
}

while (true) {

tmp = reader.readLine();
if (tmp.charAt(0) == '#') {
out.flush();
break;
}

token = new StringTokenizer(tmp);
s0 = token.nextToken();
s1 = token.nextToken();
l1 = s0.length();
l2 = s1.length();

// Levenshtein-Algorithmus zum berechnen des minimalen Abstands zweier Strings
for (i = 1; i <= l2; i++) {
for (j = 1; j <= l1; j++) {

if (s0.charAt(j - 1) == s1.charAt(i - 1)) {
d[i][j] = d[i - 1][j - 1];
} else {
d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + 1);
}
}
}

// Notwendige Operationen bestimmen
writeSolution(out, l1, l2, new StringBuilder(s1));

out.println("E");
}
}

/*
* Bestimmung die notwendigen Operationen zur Transformation des Strings
* Doina Logofatu: Grundlegende Algorithmen mit Java S.302
*/
static void writeSolution(PrintStream out, int o, int p, StringBuilder b) {

boolean flag = false;

if (o != 0 || p != 0) {
if (o > 0 && p > 0) {
if (s0.charAt(o - 1) == s1.charAt(p - 1)) {
if (d[p - 1][o - 1] == d[p][o]) {
flag = true;
writeSolution(out, o - 1, p - 1, b);
}
} else {
// Ändern eines Buchstabens
if (d[p - 1][o - 1] + 1 == d[p][o]) {
flag = true;
b.replace(p - 1, p, s1.substring(p - 1, p));
writeSolution(out, o - 1, p - 1, b);
out.print("C" + s1.substring(p - 1, p) + (p < 10 ? "0" + p : p));
}
}
}
// Einfügen eines Buchstabens
if (p > 0 && !flag) {
if (d[p][o] == d[p - 1][o] + 1) {
flag = true;
char c = b.charAt(p - 1);
b.delete(p - 1, p);
writeSolution(out, o, p - 1, b);
out.print("I" + c + "" + (p < 10 ? "0" + p : p));
}
}
// Löschen eines Buchstabens
if (o > 0 && !flag) {
if (d[p][o] == d[p][o - 1] + 1) {
b.insert(p, s0.charAt(o - 1));
writeSolution(out, o - 1, p, b);
out.print("D" + s0.charAt(o - 1) + (p + 1 < 10 ? "0" + (p + 1) : (p + 1)));
}
}
}
}

/*
* Minimum aus drei Werten finden
*/
static int min(int a, int b, int c) {
return a < b ? (a < c ? a : c) : (b < c ? b : c);
}
}