/**
 * Damerau-Levenstein-Metrik, dynamische Programmierung
 */
package de.unidu.is.irubg.ss08.blatt7;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class DamerauLevensteinDP {
    private String s1;
    private String s2;
    private int[][] mem;

    /**
     * Constructor of class.
     *
     * @param s1 the first string
     * @param s2 the second string
     */
    public DamerauLevensteinDP(String s1, String s2) {
        mem = new int[s1.length()+1][s2.length()+1];

        // Initialise mem with -1 (for undef)
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                mem[i][j] = -1;
            }
        }
        // f(0,0) = 0
        mem[0][0] = 0;

        // Put a " " before the string
        this.s1 = " " + s1;
        this.s2 = " " + s2;
    }


    /*
     * Calculate minimum
     */
    private Integer min4(int i1, int i2, int i3, int i4){
        int min = i1;
        if (min > i2) min = i2;
        if (min > i3) min = i3;
        if (min > i4) min = i4;
        return min;
    }


    /*
     * Calculate minimum
     */
    private Integer min3(int i1, int i2, int i3){
        int min = i1;
        if (min > i2) min = i2;
        if (min > i3) min = i3;
        return min;
    }

    /**
     * The "f" known from the script
     * @param i
     * @param j
     * @return The new "f" value for i and j
     */
    private int f(int i, int j) {
        int f1;
        if (mem[i][j] != -1) f1 = mem[i][j];
        else {
            if (j == 0) {
                // row 0
                f1 = i;
            }
            else if (i == 0) {
                // column 0
                f1 = j;
            }
            else if (i>2 && j>2)
                f1 =  min4(f(i-1,j)+1,
                        f(i,j-1)+1,
                        f(i-1,j-1)+ d(i,j),
                        f(i-2,j-2)+d(i-1,j)+d(i,j-1)+1);

            else
                f1 =  min3(f(i-1,j)+1,
                        f(i,j-1)+1,
                        f(i-1,j-1)+ d(i,j));

            // store result, so we don't need to calculate it again
            mem[i][j] = f1;
        }
        return f1;
    }

    /**
     * Returns the cost of transforming the first string into the second one
     * @return the cost
     */
    public int cost() {
        return f(s1.length()-1,s2.length()-1);
    }


    /**
     * d is 0, if s1[i] and s2[j] are the same, and 1 otherwise
     * @param i
     * @param j
     * @return d
     */
    private int d(int i, int j) {
        if (s1.charAt(i) == s2.charAt(j)) return 0;
        else return 1;
    }


    /**
     * Reads a line from STDIN and returns it as a String.
     *
     * @return line read from STDIN or null
     */
    private static String readln () {
     String line = null;
     try {
         BufferedReader stdin =
             new BufferedReader(new InputStreamReader(System.in));
         line = stdin.readLine();
     }
     catch (IOException io) {
         System.out.println(io.toString());
     }
     return line;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        System.out.print("\nString 1: ");
        String s1 = readln().toLowerCase().trim();
        System.out.print("\nString 2: ");
        String s2 = readln().toLowerCase().trim();
        DamerauLevensteinDP dld = new DamerauLevensteinDP(s1,s2);
        System.out.println("Cost: " + dld.cost());
    }


}