La più lunga sottosequenza comune

Un ulteriore esempio molto interessante è il problema del calcolo della sottosequenza più lunga comune a due sequenze ($lcs$). Per esempio se ho le due sequenze 'bigbugs' e 'babels' la $lcs$ è 'bbs'. Se applichiamo un approccio basato sulla forza bruta il tempo di calcolo diverebbe esponenziale, in quanto dovremmo calcolare tutte le sottosequenze della prima sequenza e confrontarle a tutte le sottosequenze della seconda.

Fortunatamente, anche in questo caso possiamo affidarci alla programmazione dinamica per risolvere il problema in un tempo polinomiale. In questo caso l'intuizione importante è quella di utilizzare i calcoli svolti in precedenza per le sottosequenze ed utilizzarli per il calcolo della nuova sottosequenza. C'è quindi da aspettarsi che anche per questo problema abbiamo bisogno di tabulare, le soluzioni parziali.

Nel caso specifico, se vogliamo avere la più lunga sottosequenza comune tra le sottosequenze 'bab' (di 'babels') e 'bigb' (di 'bigbugs'), e abbiamo calcolato la sottosequenza massima tra tutte le sottosequenze più piccole, significa che conosceremo anche la più lunga sottosequenza comune tra

• 'ba' e 'big' (la prima e la seconda più corte di un carattere)
• 'bab' e 'big' (la seconda più corta di un carattere)
• 'ba' e 'bigb' (la prima più corta di un carattere)

Da cui l'$lcs$ tra 'bigb' e 'bab' sarà ottenuta soltanto in uno dei seguenti modi

1. $lcs$ tra 'big' e 'ba' + 1 se i prossimi due caratteri sono uguali ('b'=='b')
2. oppure l'$lcs$ già ottenuta per 'big' e 'bab'
3. oppure l'$lcs$ già tra 'bigb' e 'ba'

In generale dobbiamo quindi calcolarci la sottosequenza più lunga come quella massima tra le tre possibilità precedenti. Più formalmente si avrà

$$lcs(i,j)=max \{lcs(i-1,j-1)+\delta_{s[i],t[j]}, lcs(i-1,j), lcs(i,j-1)\}$$ (7.1)

dove con $lcs(i,j)$ si intende il valore della sottosequenaza più lunga tra le sequenze $s$ e $t$, a partire dal primo carattere fino al $i$-mo e $j$-mo, rispettivamente. $\delta_{s[i],t[j]}$ è l'usuale delta di Kronecker che vale 1 se e solo se i due simboli $s[i]$ e $t[j]$ sono uguali, e vale 0 altrimenti. Dall'Equazione , tabulando i valori per le sottosequenze ( $lcs(i-1,j-1), lcs(i-1,j)$ e $lcs(i,j-1)$) ricaviamo il valore cercato in un tempo quadratico, che sarà dell'ordine di $O(len(s)*len(t))=O(mn)$, come possiamo verificare utilizzando l'algoritmo di Figura che implementa in modo diretto il calcolo posto nell'Equazione .

Figura: Calcolo della più lunga sottosequenza comune ($lcs$)

Se poi desideriamo anche avere la sottosequenza comune, dovremmo tener conto di quando i due simboli sono uguali ('='), oppure quando scartiamo i simboli della prima sequenza ('|') o della seconda ('-'). In Figura , l'algoritmo precedente è stato modificato in modo da poter tener conto anche della traccia della sottosequenza di lunghezza massima.

Figura: Calcolo della $lcs$ e relativa sottosequenza