1.


/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 526 - String Distance and Transform Process
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=467
*
* @author Dennis Wilfert
* @version 1.0, 11/30/2009
*
* Status : Accepted
* Runtime: 0.564
*/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;

class Main {

static String s0;
static String s1;
static int[][] d = new int[82][82];
static int counter;

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

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

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

tmp = reader.readLine();

while (true) {

s0 = tmp;
s1 = reader.readLine();
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);
}
}
}

// Zähler für die Nummerierung
counter = 1;
// Minimale Distanz zwischen beiden Strings
out.println(d[l2][l1]);

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

tmp = reader.readLine();
if (tmp == null) {
out.flush();
break;
}
out.println();
}
}

/*
* 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.println(counter + " Replace " + (p) + "," + s1.substring(p - 1, p));
counter++;
}
}
}
// 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.println(counter + " Insert " + (p) + "," + c);
counter++;
}
}
// 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.println(counter + " Delete " + (p + 1));
counter++;
}
}
}
}

/*
* 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);
}
}