[C++] Problema stampa LCS

[Sirik]

Buongiorno a tutti. Avrei un problema con un algoritmo che da poco ho implementato ovvero la LCS (massima sottosequenza comune). In pratica l'algoritmo è implementato correttamente e funziona alla grande ma ho un problema con la stampa, cioè in pratica mi stampa prima le parole con meno occorrenze e poi quelle con più occorrenze. So che può sembrare una cosa banale da risolvere ma mi sta mandando in tilt e vorrei risolvere senza cambiare troppo il codice che ho già implementato.

di seguito vi posto il codice:

void HashMap::LCS (string vocabolo)
{
    for (iteratore=dMap.begin(); iteratore != dMap.end() ; iteratore++)
    {
        string secondotermine = iteratore -> second ;
        int lungh1=vocabolo.size(), lungh2=secondotermine.size();
        int i=0,j=0;
        int array[100][100];
        for (int i=0; i<=lungh1; i++)
            array[i][0]=0;

        for (int j=0; j<=lungh2; j++)
            array[0][j]=0;

        for (int i=1; i<=lungh1; i++)
        {
            for (int j=1; j<=lungh2; j++)
            {
                if (vocabolo[i]==secondotermine[j])
                    array[i][j]=array[i-1][j-1]+1;
                else if (array[i-1][j]>=array[i][j-1])
                    array[i][j]=array[i-1][j];
                else
                    array[i][j]=array[i][j-1];
            }
        }
        i=lungh1, j=lungh2;
        if (array[i][j] >= 3)
            cout << "Intendevi forse " << secondotermine << "?" << endl;
    }
}

In pratica io ho un dizionario hash di parole salvate in una multimap che andrò a scorrere tutta e confronto tutte le parole nella multimap (il ciclo esterno) con quella che passo alla funzione. Lui trova le occorrenze e alla fine se sono più/uguali a 3 stampa il "suggerimento". Il programma ripeto funziona benissimo, trova le occorrenze perfettamente.Ho provato a cambiare la condizione finale ma niente, ho fatto vari tentativi ma nulla. Sapreste aiutarmi? ve ne sarei grato.
Grazie mille per l'aiuto

[MItaly]

cioè in pratica mi stampa prima le parole con meno occorrenze e poi quelle con più occorrenze

Così al volo piuttosto mi sembra che non le stampi in nessun ordine particolare, semplicemente stampa le parole con "punteggio" superiore a 3 nell'ordine in cui sono memorizzate in dMap. Se vuoi forzare un ordine specifico, memorizzale in una multimap<int, string> usando come chiave il punteggio della parola, e stampale tutte alla fine, iterando sulla multimap al contrario (ovvero partendo dalle chiavi più alte - match migliore - e andando verso quelle più basse).

P.S.: mi sono permesso di sistemare l'indentazione del codice, tutti quei cicli senza alcuna indentazione erano decisamente poco chiari...

[Sirik]

il problema è che la chiave nella mia multimap nel mio caso deve corrispondere al valore di una funzione hash. Tu mi stai dicendo di fare una nuova multimap? o di lavorare e assegnare i punteggi sulla vecchia? Grazie infinite per l'aiuto e grazie per aver aggiustato il codice.

[MItaly]

Dico di fare un'altra multimap temporanea, locale semplicemente alla funzione, da usare solo per memorizzare e tener ordinati i risultati da mostrare.

[Sirik]

ho provato a fare una cosa del genere

   if (array[i][j] >= 3) 
     { 
             dMap2.insert(pair<int,string>(array[i][j],secondotermine)); 
     } 

    for (iteratore2=dMap2.end(); iteratore2 != dMap2.begin() ; iteratore2--) 
     { 
             cout << "Forse intendevi " << secondotermine <<"?"<<endl;  
     }

in pratica se le occorrenze sono più o uguali a 3 lui salva nella dMap2 il valore delle occorrenze e il termine. Questo però nn mi da un ordine nella dMap2 o sbaglio? devo ordinarla in seguito forse?
Poi ho provato a iterarla al contrario come suggerito però il risultato nn cambia. Forse sbaglio ad accedere al valore. HELP

Grazie infinite ancora per l'aiuto

[MItaly]

Originariamente inviato da Sirik
in pratica se le occorrenze sono più o uguali a 3 lui salva nella dMap2 il valore delle occorrenze e il termine. Questo però nn mi da un ordine nella dMap2 o sbaglio? devo ordinarla in seguito forse?

La multimap è un contenitore intrinsecamente ordinato rispetto alle chiavi, per cui dovresti già ottenere un output ordinato.

Poi ho provato a iterarla al contrario come suggerito però il risultato nn cambia. Forse sbaglio ad accedere al valore. HELP

Posta il codice modificato.

[Sirik]

il codice è cosi:

void HashMap::LCS (string vocabolo) 
{ 
      for (iteratore=dMap.begin(); iteratore != dMap.end() ;iteratore++) 
             { 
                 string secondotermine = iteratore -> second ; 
                 int lungh1=vocabolo.size(), lungh2=secondotermine.size(); 
                 int i=0,j=0; int array[100][100]; 
                 for (int i=0;i<=lungh1;i++) 
                       { 
                               array[i][0]=0; 
                       } 
                 for (int j=0;j<=lungh2;j++) 
                       { 
                               array[0][j]=0; 
                       } 
                 for (int i=1;i<=lungh1;i++) 
                       { 
                           for (int j=1;j<=lungh2;j++) 
                                 { 
                                      if (vocabolo[i]==secondotermine[j]) 
                                            { 
                                                  array[i][j]=array[i-1][j-1]+1;  
                                             } 
                                       else if (array[i-1][j]>=array[i][j-1]) 
                                             { 
                                                  array[i][j]=array[i-1][j]; 
                                             } 
                                       else { 
                                                   array[i][j]=array[i][j-1]; 
                                              } 
                                    } 
              }
               i=lungh1, j=lungh2; 

               if (array[i][j] >= 3) 
                    { 
                          dMap2.insert(pair<int,string>(array[i][j],secondotermine));    
                    } 
               } 
              
                for (iteratore2=dMap2.end(); iteratore2 != dMap2.begin() ;iteratore2--) 
                     { 

                           cout << "Forse intendevi " << iteratore2 -> second<<"?"<<endl; 
                      } 
}

Ho seri dubbi sul for finale infatti il programma crasha.
Allora secondo me l'ultimo if è fatto bene perchè in pratica tuttle parole con x occorenze le salva nella dMap2 con il valore dell'occorrenza. Poi alla fine il ciclo dovrebbe stamparle tutte ma nn ho capito bene come accedere agli elementi della multimap. Poi vabbe credo manchi il fatto che alla fine dell'algoritmo devo svuotarla la dMap2, giusto?
Cmq cm posso risolvere il problema della stampa?
Grazie ancora

[MItaly]

Il for è impostato in maniera scorretta: gli iteratori begin/end identificano rispettivamente il primo elemento e un elemento "immaginario" dopo l'ultimo, per cui se provi a dereferenziare l'iteratore fornito da end ottieni un crash (se sei fortunato); inoltre, la condizione iteratore2!=dMap2.begin() è sbagliata, dato che in tal caso il ciclo salta il primo elemento.

In generale iterare al contrario con gli iteratori "normali" è scomodo - ed è per questo che esistono gli iteratori "reverse": usa rbegin() (reverse begin) e rend() (reverse end)

for(multimap<int, string>::reverse_iterator it=dMap2.rbegin(); it!=dMap2.rend(); ++it)
    cout << "Forse intendevi " << it->second<<"?"<<endl;

Poi vabbe credo manchi il fatto che alla fine dell'algoritmo devo svuotarla la dMap2, giusto?

Limitati a dichiarare dMap2 come variabile locale alla funzione: al termine della funzione la variabile viene distrutta e la sua memoria viene deallocata dinamicamente.

Infine, due appunti:

• non hai dichiarato iteratore e iteratore2 - il che mi fa pensare che tu li abbia messi come membri della classe o, peggio, globals; evita: tutto quello che serve semplicemente per la durata di una funzione (ovvero, non fa parte dello stato dell'oggetto) va dichiarato locale alla funzione;
• anche l'indentazione di quest'ultimo blocco è un po' teribbile... dovresti curarla un po' di più, in modo da rendere il codice più comprensibile; non è difficile, scegli uno stile di indentazione coerente (io personalmente sono per lo stile Allman) e imposta il tuo editor/IDE in modo che lo rispetti e ti aiuti a scrivere il codice in maniera ordinata.

[Sirik]

ho risolto. Ho seguito il tuo consiglio e ho finalmente capito come iterare al contrario la multimap, ora funziona alla grande, mi stampa le parole nell'ordine che dico io ^^.

Sei stato davvero cordiale e gentile e scusa ancora la mia totale ignoranza sull'argomento, sono alle prime armi e sto cercando di imparare il più possibile
Seguirò sicuramente i tuoi consigli sullo stile .

Grazie ancora e buon lavoro

[MItaly]