[C++] Trovare la massima sottosequenza palindroma

doublechar/ luglio 11, 2017/ Developing/ 0 comments

In questa serie di articoli sulla programmazione competitiva affronteremo vari algoritmi, specialmente di programmazione dinamica, molto usati nei vari contest e spesso utili nei colloqui di lavoro.

Massima sottosequenza palindroma

Che vuol dire palindroma? Significa che la stringa, il numero, qualsiasi cosa a cui ci riferiamo, può essere letta indipendentemente da sinistra verso destra o viceversa.

Esempi: avevi, ingegni o anche numeri come 1629261, 9339, 1.

Che vuol dire sottosequenza? Significa che per formare la stringa palindroma possiamo prendere casualmente i vari caratteri/numeri mantendone però l’ordine.

Per esempio, la massima sottosequenza palindroma di howorks è semplicemente owo.
Altro esempio: programmazione, oammao

Vedremo vari approcci di diversa complessità per risolvere questo problema.

Soluzione Naive

L’algoritmo più semplice da pensare e da implementare (forse) è quello che prova tutti i 2N
sottoinsiemi esistenti
per poi verificare quale sia palindromo e ritornarlo.

Ci basterà salvare in un array globale quali elementi scegliamo.

Questo è il codice commentato:

Soluzione migliorata

Con questo algoritmo non saremo in grado di risolvere il problema con stringhe di lunghezza 50 o 100 caratteri.
Possiamo pensare invece ad una soluzione migliore della precedente facendo un paio di assunzioni.

  • Ogni carattere è palindromo
  • Se abbiamo una sequenza palindroma di lunghezza L e aggiungiamo due lettere uguali all’inizio e alla fine avremo come risultante una lunghezza di L+2.

Adesso se possiamo salvare da qualche parte quali sottosequenze abbiamo e qual è la loro risposta a questo problema potremmo risolverlo in tempo N2, migliorando notevolmente la soluzione precedente.

Partiamo da questo esempio: ciai.

Sappiamo che tutte le sottosequenza di lunghezza 1 sono c, i, a, i.

Se prendessimo le sottosequenza di lunghezza 2 avremo ci, ia, ai, tra questi il massimo sarebbe sempre 1.

Con lunghezza 3 invece ecco la magia: cia, iai. In questo momento sappiamo che a ha lunghezza massima 1 (l’abbiamo calcolata prima, è un caso che sia una sola lettera, potrebbe benissimo essere una sottosequenza qualsiasi) ma la lettera iniziale e finale è uguale.

A questo punto ci basta prendere la lunghezza dalla sottosequenza massima [i+1, j-1] dove i e j sono l’indice dell’inizio e della fine di iai (praticamente prenderemmo soltanto a) e sommare 2 (perché stiamo aggiungendo una lettera sia all’inizio che alla fine) a questo risultato. Avremo tre.

Alla fine proviamo con lunghezza 4, abbiamo soltanto una sottosequenza ciai, prenderemo semplicemente il risultato di iai e siccome la c non fa alcune differenza non aggiungeremo niente.

Useremo una matrice per salvare le nostre lunghezze, avremo complessità N2 sia spazialmente che temporalmente.

Questo è l’algoritmo implementato:

Conclusione

Per qualsiasi dubbio potete contattarci utilizzando i commenti o le nostre pagine social.

Facci sapere cosa ne pensi con un commento!