Dopo tanto tempo riprendo questo thread perchè son riuscito dopo varie ricerche a stampare la distanza minima di editing tra due stringhe ma ho qualche difficoltà nello scorrere la latrice per identificare le operazioni .
posto tutto il codice se qualcuno riesce a darci un occhiata e darmi qualche suggerimento ....
import java.util.ArrayList;
import java.util.Arrays;
public class DistanzaDiEditing {
private static int[][] matriceDiAdiacenza ;
public static String distanza(String str1,String str2){
String operazioni=" op: ";
int lunghezza1 = str1.length();
int lunghezza2 = str2.length();
matriceDiAdiacenza = new int[lunghezza1+1][lunghezza2+1];
int match;
/*riempimento della riga 0 della matrice di adiacenza*/
for(int i = 0 ; i <= lunghezza1 ; i++){
matriceDiAdiacenza[i][0]=i;
}
/*riempimento della colonna 0 della matrice di adiacenza*/
for(int j = 0 ; j <= lunghezza2 ;j++){
matriceDiAdiacenza[0][j]=j;
}
/*Calcolo della distanza tra tutte le sottosringhe delineate nella matrice*/
for(int i = 1 ; i <= lunghezza1 ;i++){
for( int j=1 ;j <= lunghezza2 ; j++){
//valuto se i caratteri son uguali
if(str1.charAt(i-1)==str2.charAt(j-1)){
match = 0;
}else{
match = 1;
}
matriceDiAdiacenza[i][j]=Math.min(matriceDiAdiacenza[i-1][j]+1// costo cancellazione
,Math.min(matriceDiAdiacenza[i][j-1]+1,//costo inserzione
matriceDiAdiacenza[i-1][j-1]+match));// costo sostituzione
if(i>1 && j>1 && str1.charAt(i-1)==str2.charAt(j-2)&&str1.charAt(i-2)==str2.charAt(j-1)){
matriceDiAdiacenza[i][j]= Math.min(matriceDiAdiacenza[i][j],matriceDiAdiacenza[i-2][j-2]+match);//costo scambio
}
// System.out.print(matriceDiAdiacenza[i-1][j-1]+"\t");
}
}
for(int i = 0 ; i < matriceDiAdiacenza.length ;i++){
for(int j=0 ;j <matriceDiAdiacenza[i].length ; j++){
System.out.print(matriceDiAdiacenza[i][j]+"\t");
}
// System.out.print(matriceDiAdiacenza[i][0]+"\n");
System.out.print("\n");
}
int k = 0;
int h = 0;
for( k=1,h=1 ; k < matriceDiAdiacenza.length ;k++,h++){
//if(k>1 && h>1 && str1.charAt(k-1)==str2.charAt(h-2)&&str1.charAt(k-2)==str2.charAt(h-1))
if(matriceDiAdiacenza[k][h]== (matriceDiAdiacenza[k][h-1])){
operazioni += "canc("+ k + ") ";
if(k < matriceDiAdiacenza.length-1)
k++;
}
}
return matriceDiAdiacenza[lunghezza1][lunghezza2] +"\n" +operazioni;
}
}
in particolare in questa parte
int k = 0;
int h = 0;
for( k=1,h=1 ; k < matriceDiAdiacenza.length ;k++,h++){
//if(k>1 && h>1 && str1.charAt(k-1)==str2.charAt(h-2)&&str1.charAt(k-2)==str2.charAt(h-1))
if(matriceDiAdiacenza[k][h]== (matriceDiAdiacenza[k][h-1])){
operazioni += "canc("+ k + ") ";
if(k < matriceDiAdiacenza.length-1)
k++;
}
}
che mi lancia un eccezione se ci son più di due caratteri cancellati