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

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

public class DamerauLevensteinRekursiv {
    private String s1;
    private String s2;

    /**
     * Constructor of class.
     *
     * @param s1 the first string
     * @param s2 the second string
     */
    public DamerauLevensteinRekursiv(String s1, String s2) {
        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 (i == 0 && j == 0) f1 = 0;
        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));
        }
        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();
        DamerauLevensteinRekursiv dlr = new DamerauLevensteinRekursiv(s1,s2);
        System.out.println("Cost: " + dlr.cost());
    }



}