package Blatt2;

public class Distance {
	
	//****************************
	  // Finde Min aus drei Werte
	  //****************************
	

	  // static int Minimum (int a, int b, int c) {
	  //int mi;

//	    mi = a;
	//    if (b < mi) {
	  //    mi = b;
	    //}
	    //if (c < mi) {
	      //mi = c;
	    //}
		//return mi;
	   

	  //}

	  //*****************************
	  // Ähnlichkeit Matrix 
	  //*****************************
	  public static void main(String[] args) {
	  String q = "RHABARBER" ;
	  String s = "BARBARA" ;
	 //String	q = "MULTIMEDIADATENBANKENÜBUNGSAUFGABE";
	 //String	s = "DATENBANKENMULTIMEDIAABFRAGE"; 
     //String q = "PEERFPMMSTFKVLLCGAVLSRVDAGQEQLGRR" ;
	 //String s = "ADERFPMMSTFKVVLCGAVLARVDAGDEQLERK" ;
	  
	  int n; // length of q
	  int m; // length of s
	  int [][] d; // matrix
	  int i; // iterates through q
	  int j; // iterates through s
	  char q_i; // ith character of q
	  char s_j; // jth character of s
	  int cost; // cost

	    // Step 1

	    n = q.length ();
	    m = s.length ();
	    if (n == 0) {
	    	n = 0;

	    }
	    if (m == 0) {
	    	 m = 0;

	    }
	   d = new int[n+1][m+1];

	    // Step 2

	    for (i = 0; i <= n; i++) {
	      d[i][0] = i;
	    }

	    for (j = 0; j <= m; j++) {
	      d[0][j] = j;
	    }

	    // Step 3

	    for (i = 1; i <= n; i++) {

	      q_i = q.charAt (i - 1);
	      //d[i][1] = q_i;
	      
	      // Step 4

	      for (j = 1; j <= m; j++) {

	        s_j = s.charAt (j - 1);
	        //d[1][j] = s_j;
	        // Step 5

	        if (q_i == s_j) {
	          cost = 0;
	        }
	        else {
	          cost = 1;
	        }

	        // Step 6

	        d[i][j] = Math.min(Math.min 
	        		(d[i-1][j]+1, d[i][j-1]+1), d[i-1][j-1] + 
	        		cost);
		    System.out.println(d[i][j]+"");
		    System.out.println();
	      }


	    }
		//return d[n][m];
	    System.out.println(d[n][m]+"");
	    // Step 7

	    


	    
	  }
	  
	    
	}