Un ulteriore esempio molto interessante è il problema del calcolo
della sottosequenza più lunga comune a due sequenze (). Per esempio
se ho le due sequenze 'bigbugs' e 'babels' la
è '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
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.