[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...

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