Partiamo dal presupposto di ordinare, come detto in precedenza, le stringhe in ordine decrescente di lunghezza e le stringhe della stessa lunghezza le ordiniamo in ordine alfabetico.
La sequenza s:
abacd bcdada dd abcd bcdd adcd addd aa ccd add ad
si trasforma in:
bcdada abacd abcd adcd addd bcdd add ccd aa ad dd
Se adesso consideriamo le condizioni imposte dall’esercizio per muoverci da una parola ad un’altra, ossia:
• w2 is obtained from w1 by deleting one letter.
• w2 is obtained from w1 by replacing one of the letters
in w1 by some letter that appears to its right in w1 and which is also to its right in alphabetical
order.
Possiamo notare che partendo da una delle nostre stringhe possiamo “saltare” solamente su delle stringhe alla sua destra.
Quello che diventa utile fare è tenersi un array(solitamente chiamato soluzioni), nel quale ad ogni casella i andremo ad inserire la lunghezza della sequenza più lunga che termina in i.
int soluzioni[MAXN];
for(int i=0;i<n;i++) soluzioni[i]=1; //sicuramente una sequenza che comprende la stringa i è lunga al minimo 1(solo lei stessa)
Quello che possiamo sicuramente dire riguardo a questo esercizio è: se dalla stringa i che sto analizzando posso arrivare alla stringa j allora posso dire che una sequenza che termina in j è lunga soluzioni[i]+1, quindi la sequenza che finiva con la stringa i ma aggiungendogli anche la stringa j.
Guarda se ti bastano queste indicazioni per trovare la soluzione altrimenti guarda pure lo spoiler che però rivela gran parte della soluzione.
Esempio:
bcdada abacd abcd adcd addd bcdd add ccd aa ad dd
I due cicli possono essere visti come:
for(int i=1;i<n;i++)
for(int j=0;j<i;j++)
if(jump(j,i)==true && soluzioni[j]>=soluzioni[i])
soluzioni[i]=soluzioni[j]+1;
Come detto le soluzioni di queste stringhe partono inizialmente da 1:
parto analizzando la seconda stringa quindi abacd, è “concatenabile” con la stringa in posizione 0? La risposta è no, quindi la sequenza più lunga che finisce in abacd è lunga 1(la strinfa stessa)
La i aumenta a 2, parto sempre confrontando con la numero 0:
partendo dalla stringa 0 posso arrivare alla 2?No, quindi nulla
partendo dalla stringa 1 posso arrivare alla 2?La risposta è si, allora la sequenza di lunghezza massima che termina con la stringa numero 2 sarà lunga 2( soluzioni[j]+1).
continuo a ripetere questo procedimento per ogni valore, alla fine la soluzione del nostro problema sarà data dal valore massimo inserito all’interno dell’array soluzioni.
Spero di essere stato il più chiaro possibile.
