«

»

feb 06

Determinare la lunghezza della più lunga sottostringa palindroma

Determinare la lunghezza della più lunga sottostringa palindroma ( Appello Aprile 2010)

Il testo recita:

Data una stringa S = a1 a2 . . . an di n caratteri, si propone il problema di determinare la lunghezza della più lunga palindroma sottostringa di S.

Suggerimento:

per la risoluzione: Sia l[i, j] la lunghezza della più lunga palindroma contenuta nella stringa S[i . . . j] = ai ai+1 . . . aj . Il caso base consiste in una stringa di 0 caratteri, cioè il caso in cui i > j. Altrimenti se i caratteri S[i] ed S[j] sono uguali allora posso controllare se la stringa S[i + 1 . . . j − 1] e palindroma ed eventualmente aggiungere i due caratteri S[i] ed S[j]. In tutti gli altri casi devo risolvere ricorsivamente i problemi l[i + 1, j] e l[i, j − 1] e prendere il massimo. La definizione ricorsiva di una soluzione ottima potrebbe essere così definita

La risoluzione del problema mediante l’utilizzo della programmazione dinamica prevede quindi la costruzione di una tabella di dimensione n × n.Si richiede di implementare in linguaggio C:

  1. a) Una funzione lr che calcoli l[1, n] ossia la lunghezza della piùlunga palindroma contenuta nell’intera stringa ;
  2. b) Una funzione lrd che calcoli l[n, k] in O(n2 );

Implementazione Ricorsiva

int m(char s[], int da, int a)
{
    int x;
    if(da>a)return 0;
    if(da==a)return 1;
    if (s[a]==s[da]){
        x=m(s,da+1, a-1);
        if(x==a-da-1)return x+2;
    }
    int r=m(s,da+1,a);
    int l=m(s,da,a-1);
    x=r-l;
    if(x>0)
        return r;
    else
        return l;
}

La fuzione viene implementata applicando semplicemente la formula di ricorsione

Implementazione dinamica

int m_d(char s[], int da, int a,int n,int k, int v[n][k])
{
    int x;
    if(da>a)return 0;
    if(da==a)return 1;
    if (s[a]==s[da]){
        x=v[da+1][a-1];
        if(x==a-da-1)return x+2;
    }
    int r=v[da+1][a];
    int l=v[da][a-1];
    x=r-l;
    if(x>0)
        return r;
    else
        return l;
}

int m_iterativa(char stringa[])
{
    int len=strlen(stringa);
    int **v=malloc(sizeof(int)*len*len);
    int i,j;
    for(i=0;i<len;i++){
        for(j=0;j<(len-i);j++){
            int pal=m_d(stringa,j,i+j,len,len,v);
            v[j*len+(i+j)]=pal;
        }
    }
    len=v[len-1];
    free(v);
    return len;
}

L’implementazione dinamica viene creata modificando la funzione ricorsiva in modo che i valori già calcolati vengano letti da una matrice invece che ricalcolati. I valori per cui c<r (quelli sopra sotto la diagonale principale) sono necessariamente 0 e non vanno calcolati.

L’unico modo di percorrere la matrice senza creare dipendenze da valori non ancora calcolati è per diagonali.

Esempi di matrici dei valori parziali

[
[ 1   1   1   1   3   5   5 ]
[ 0   1   1   1   3   5   5   ]
[ 0   0   1   1   3   3   3   ]
[ 0   0   0   1   1   1   1   ]
[ 0   0   0   0   1   1   1   ]
[ 0   0   0   0   0   1   1   ]
[ 0   0   0   0   0   0   1   ]
]
pabcbaq -> 5
[
[ 1   1   2   4   4   4   4   4   4   4   4   4   4 ]
[ 0   1   2   2   2   2   4   4   4   4   4   4   4   ]
[ 0   0   1   1   1   2   4   4   4   4   4   4   4   ]
[ 0   0   0   1   1   2   4   4   4   4   4   4   4   ]
[ 0   0   0   0   1   2   2   2   3   3   3   3   3   ]
[ 0   0   0   0   0   1   1   1   3   3   3   3   3   ]
[ 0   0   0   0   0   0   1   1   3   3   3   3   3   ]
[ 0   0   0   0   0   0   0   1   1   1   3   3   3   ]
[ 0   0   0   0   0   0   0   0   1   1   3   3   3   ]
[ 0   0   0   0   0   0   0   0   0   1   1   3   3   ]
[ 0   0   0   0   0   0   0   0   0   0   1   1   1   ]
[ 0   0   0   0   0   0   0   0   0   0   0   1   1   ]
[ 0   0   0   0   0   0   0   0   0   0   0   0   1   ]
]
ammaccabanane -> 4
Share Button

2 comments

  1. gabriele

    Ciao
    credo che la funzione ricorsiva non corrisponda agli esempi che hai postato sotto.
    Se dici che i valori per i>j ( oppure c<r ) valgono 0, allora gli esempi non corrispondono o non riesco a capire io.
    perchè la 'i' indica le righe della matrice e 'j' le colonne, giusto?

    1. Vincenzo La Spesa

      Hai ragione! c’era un bug nella procedura che stampava le matrici, il ciclo for che iterava le righe scorreva al contrario.
      L’ho corretto.

Commenti disabilitati.