[JAVA] Il problema dell'LCS

[BreV&]

Salve a tutti, questo è il mio primo post in questa sezione...
...chissà quanti ne avete visti come me...
...venerdì si consegna e non riesco a finire il programma :(

Dunque, il problema è il classico LCS (Longest Common Subsequence), però al posto della classica ricostruzione della soluzione ottima, io devo stampare TUTTE le soluioni ottime...
...e non so da dove cominciare... :cry:


import java.io.*;

public class Lcs
{
public void stampaMat(int[][] mat, int n, int m)
{
for(int i=1; i<n; i++)
{
for(int j=1; j<m; j++)
System.out.print(mat[i][j]);
System.out.println();
}
System.out.println();
}

public void stampaMat(char[][] mat, int n, int m)
{
for(int i=1; i<n; i++)
{
for(int j=1; j<m; j++)
System.out.print(mat[i][j]);
System.out.println();
}
System.out.println();
}

public int[][] minit(int n, int m) //matrice init
{
int[][] mat = new int[n][m];
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
mat[i][j]=0;
return mat;
}
public char[][] sinit(int n, int m) //soluzione init
{
// [D]iagonal [L]eft [U]p
char[][] sol = new char[n][m];
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
sol[i][j]='X';
return sol;
}


public char[][] fill(int[][] mat, char[][] sol,String a, String b, int n, int m)
{
for (int i=1; i<n; i++)
{
for(int j=1; j<m; j++)
{
if (a.charAt(i-1) == b.charAt(j-1))
{
sol[i][j]='D';
mat[i][j]=(mat[i-1][j-1]) + 1;
}
else if (mat[i-1][j] > mat[i][j-1])
{
sol[i][j]='U';
mat[i][j]=mat[i-1][j];
}
else
{
sol[i][j]='L';
mat[i][j]=mat[i][j-1];
}
}
}
return sol;
}

public void stampaLCS(char[][] sol, String word, int i, int j)
{
if (i == 0 || j == 0)
{
System.out.println("*");
return;
}
else if (sol[i][j] == 'D')
{
stampaLCS(sol, word, i-1, j-1);
System.out.print(word.charAt(i-1));
}
else if (sol[i][j] == 'U') stampaLCS(sol, word, i-1, j);
else stampaLCS(sol, word, i, j-1);
}

public static void main (String args[])throws IOException
{
//legge da file le parole
File f=new File(args[0]);
FileInputStream fis=new FileInputStream(f);
InputStreamReader isr=new InputStreamReader(fis);
BufferedReader br=new BufferedReader(isr);
String primaParola=br.readLine();
String secondaParola=br.readLine();
System.out.println(primaParola);
System.out.println(secondaParola);
System.out.println();
//istanzia e inizializza le due matrici
int n=(primaParola.length()+1);
int m=(secondaParola.length()+1);
Lcs lcs = new Lcs();
int [][]matrice = lcs.minit(n,m);
char [][]soluzione = lcs.sinit(n,m);
lcs.stampaMat(matrice,n,m);
lcs.stampaMat(soluzione,n,m);
//manipola le matrici
soluzione = lcs.fill(matrice,soluzione,primaParola,secondaParola,n,m);
lcs.stampaMat(matrice,n,m);
lcs.stampaMat(soluzione,n,m);
//stampa le soluzioni
lcs.stampaLCS(soluzione,primaParola,n-1,m-1);
System.out.println();
}
}


questo è quanto ho scritto (e gira), un ringraziamento di cuore a chi mi saprà aiutare...

[cionci]

Devi darci più indizi... Spiega dove sta il problema nel tuo codice... Cosa non ti riesce ?

[BreV&]

dunque, nel mio codice non ci sono problemi, prechè quello è il classico LCS, dove grazie al metodo "stampaLCS" percorro all'indietro la matrice che ho compilato con il metodo "fill" e stampo a video una delle possibili soluzioni ottime. Il mio problema è che il testo dell'esercizio mi richiede la stampa a video di TUTTE le soluzioni ottime e io non ho la più pallida idea di come implementarlo :(
Mi basterebbe anche solo un "punto di partenza" come quelli che ho visto dare più volte in 3D di questa sezione :)