import java.util.*;
public class EditDistance {
    int COST_M = 0, COST_S = 1, COST_D = 1, COST_I = 1;
    public static final int OP_M = 1, OP_S = 2, OP_I = 4, OP_D = 8;
    String s,t;
    int[][] cost, op;
    public EditDistance(String s,String t) { this.s = s; this.t = t; }
    public void setSubstituteCost(int COST_S) { this.COST_S = COST_S; }
    public void setInsertCost(int COST_I) { this.COST_I = COST_I; }
    public void setDeleteCost(int COST_D) { this.COST_D = COST_D; }
    public int solve() {
	cost = new int[s.length()+1][t.length()+1];
	cost[0][0] = 0;
	op = new int[s.length()+1][t.length()+1];
	op[0][0] = 0;
	for (int i=1; i<cost.length; i++) {
	    cost[i][0] = cost[i-1][0] + COST_D;
	    op[i][0] = OP_D;
	}
	for (int i=1; i<cost[0].length; i++) {
	    cost[0][i] = cost[0][i-1] + COST_I;
	    op[0][i] = OP_I;
	}
	for (int si=1; si<cost.length; si++) {
	    for (int ti=1; ti<cost[0].length; ti++) {
		int c_m = (s.charAt(si-1) == t.charAt(ti-1)) ? cost[si-1][ti-1] + COST_M : Integer.MAX_VALUE;
		int c_s = cost[si-1][ti-1] + COST_S;
		int c_i = cost[si][ti-1] + COST_I;
		int c_d = cost[si-1][ti] + COST_D;
		cost[si][ti] = Math.min(c_m,Math.min(c_s,Math.min(c_i,c_d)));
		op[si][ti] = 0;
		if (cost[si][ti] == c_m) op[si][ti] |= OP_M;
		if (cost[si][ti] == c_s) op[si][ti] |= OP_S;
		if (cost[si][ti] == c_i) op[si][ti] |= OP_I;
		if (cost[si][ti] == c_d) op[si][ti] |= OP_D;
	    }
	}
	return cost[s.length()][t.length()];
    }
    public String[] getPath() {
	ArrayList<String> v = new ArrayList<String>();
	int si=cost.length-1;
	int ti=cost[0].length-1;
	while (si > 0 || ti > 0) {
	    if ((op[si][ti] & OP_M) != 0) {
		v.add("matches '"+s.charAt(si-1)+"' and '"+t.charAt(ti-1)+"'");
		si--; ti--;
	    } else if ((op[si][ti] & OP_S) != 0) {
		v.add("substitute '"+s.charAt(si-1)+"' by '"+t.charAt(ti-1)+"'");
		si--; ti--;
	    } else if ((op[si][ti] & OP_I) != 0) {
		v.add("insert '"+t.charAt(ti-1)+"'");
		ti--;
	    } else if ((op[si][ti] & OP_D) != 0) {
		v.add("delete '"+s.charAt(si-1)+"'");
		si--;
	    } else throw new RuntimeException("bad op");
	}
	Collections.reverse(v);
	return v.toArray(new String[0]);
    }
    public String showCostTable() { return toString(cost); }
    public String showOpTable() { return toString(op); }
    public String toString(int[][] x) {
	StringBuilder sb = new StringBuilder(" |   ");
	for (int i=0; i<t.length(); i++) sb.append("  "+t.charAt(i));
	int w = sb.toString().length();
	sb.append("\n");
	for (int i=0; i<w; i++) sb.append((i==1) ? "+" : "-");
	sb.append("\n");
	for (int line=0; line < x.length; line++) {
	    if (line == 0) sb.append(" | ");
	    else sb.append(s.charAt(line-1)+"| ");
	    for (int col=0; col < x[line].length; col++) {
		int v=x[line][col];
		if (v < 10 && v>=0) sb.append(" ");
		sb.append(v + " ");
	    }
	    sb.append("\n");
	}
	return sb.toString();
    }
}