Esercizio - sottosequenza antipalindroma di lunghezza massima (compito del 9 luglio 2025, es. 2)

Fonte: compito di Algoritmi per l'Ingegneria, Ing. Informatica UniPD, 9 luglio 2025, seconda parte, esercizio 2 (17 punti).

Testo

Una stringa $Z = \langle z_1, z_2, \dots, z_k \rangle$ si dice antipalindroma se ha lunghezza pari e, per $k \ge 2$, soddisfa la relazione $z_{1+h} \ne z_{k-h}$ per $0 \le h \le k - 1$. (Dunque $Z = \epsilon$ è antipalindroma; le stringhe di lunghezza dispari non sono antipalindrome.)

Data in ingresso una arbitraria stringa $X$ di lunghezza $n \ge 1$ definita su un qualche alfabeto $\Sigma$, si vuole determinare la lunghezza di una Sottosequenza Antipalindroma di Lunghezza Massima ($\text{SALM}(X)$). (Si osservi che tale lunghezza sarà sempre un numero pari.)

• (a) [6 punti] Si provi una proprietà di sottostruttura ottima per il problema sullo spazio $\{X_{i..j} : 1 \le i \le j \le n\}$ delle sottostringhe di $X$.
• (b) [3 punti] Si fornisca una ricorrenza sulla lunghezza della $\text{SALM}(X_{i..j})$ di una generica sottoistanza $X_{i..j}$.
• (c) [5 punti] Si fornisca lo pseudocodice bottom-up iterativo COMPUTE_SALM(X) che, data in ingresso una stringa $X = \langle x_1, \dots, x_n \rangle$, restituisca la lunghezza di una SALM$(X)$, argomentandone la correttezza.
• (d) [3 punti] Sia $T(n)$ il numero di confronti tra caratteri dell'alfabeto $\Sigma$ eseguiti dall'algoritmo sviluppato al punto (c). Si valuti $T(n)$ esattamente.

Soluzione

Cosa significa "antipalindroma"

Gli estremi simmetrici sono sempre diversi: $z_1 \ne z_k$, $z_2 \ne z_{k-1}$, e così via. Se $k$ è dispari l'elemento centrale ($h = (k-1)/2$) dovrebbe essere diverso da sé stesso, impossibile: per questo le antipalindrome hanno lunghezza pari. Per esempio $\langle a, b \rangle$, $\langle a, b, c, d \rangle$ e $\langle a, b, a, b \rangle$ (coppie $(a,b)$ e $(b,a)$) sono antipalindrome; $\langle a, b, c, a \rangle$ no, perché $z_1 = z_4$; $\langle a, b, a \rangle$ no, perché ha lunghezza dispari. È la variante "opposta" della sottosequenza palindroma più lunga (Allineamento di stringhe e sottosequenza palindroma più lungadue problemi di DP su stringhe con la stessa struttura della LCS. Allineamento ottimo di due stringhe di DNA con matrice di score S e penalità di gap g: C(i,j) = max{C(i-1,j-1) + s(x_i,y_j), C(i-1,j) + g, C(i,j-1) + g}, C(i,0) = i g, C(0,j) = j g; Theta(mn) tempo, spazio Theta(min{m,n}) con un solo vettore se serve solo il costo. Sottosequenza palindroma più lunga (LPS) sullo spazio delle sottostringhe X_(i..j): p(i,j) = 2 + p(i+1,j-1) se x_i = x_j, altrimenti max{p(i+1,j), p(i,j-1)}; scansione per diagonali, n(n-1)/2 confronti.Allineamento di stringhe e sottosequenza palindroma più lunga →), con la stessa struttura: si tolgono i due estremi, quindi lo spazio naturale è quello delle sottostringhe.

(a) Proprietà di sottostruttura ottima

Proprietà. Per ogni $1 \le i \le j \le n$ esiste una $Z = \text{SALM}(X_{i..j})$ tale che:

1. se $i = j$, $Z = \epsilon$;
2. se $j = i + 1$ e $x_i = x_j$, $Z = \epsilon$;
3. se $j = i + 1$ e $x_i \ne x_j$, $Z = \langle x_i, x_j \rangle$;
4. se $j > i + 1$ e $x_i \ne x_j$, allora $z_1 = x_i$, $z_k = x_j$ e $Z_{2..k-1}$ è una $\text{SALM}(X_{i+1..j-1})$;
5. se $j > i + 1$ e $x_i = x_j$, allora $Z$ è una $\text{SALM}(X_{i+1..j})$ oppure una $\text{SALM}(X_{i..j-1})$ (la più lunga delle due).

Osservazione. Nel punto 4 si afferma che esiste una SALM che ha $x_i$ e $x_j$ come estremi, non che tutte le SALM li abbiano: l'enunciato più forte sarebbe falso. Per esempio in $X = \langle a, c, b \rangle$ ($x_1 = a \ne b = x_3$) le SALM sono $\langle a, c \rangle$, $\langle a, b \rangle$ e $\langle c, b \rangle$, tutte di lunghezza $2$, ma solo $\langle a, b \rangle$ ha $z_1 = x_1$ e $z_2 = x_3$. L'enunciato debole basta per un algoritmo corretto, come per la scelta greedy: serve che esista almeno una soluzione ottima con la proprietà.

Dimostrazione. I punti 1, 2 e 3 (sottostringhe di lunghezza $1$ o $2$) sono banali, e in quei casi $Z$ è unica: una stringa di un solo carattere non ha sottosequenze antipalindrome non vuote (hanno lunghezza dispari); per due caratteri uguali nessuna coppia è diversa; per due caratteri diversi $\langle x_i, x_j \rangle$ è antipalindroma e massima.

Sia ora $j > i + 1$ (almeno $3$ caratteri) e sia $Z' = \langle x_{j_1}, \dots, x_{j_k} \rangle$ una SALM qualsiasi di $X_{i..j}$, con $i \le j_1 < \dots < j_k \le j$.

Punto 4, $x_i \ne x_j$. Prima di tutto $Z' \ne \epsilon$: altrimenti $\langle x_i, x_j \rangle$ sarebbe una sottosequenza antipalindroma di lunghezza $2$, più lunga. Quindi $k \ge 2$. Si costruisce $Z$ a partire da $Z'$ sostituendo, se $j_1 > i$, il primo carattere con $x_i$ (usando l'indice $i < j_1$) e, se $j_k < j$, l'ultimo con $x_j$ (usando l'indice $j > j_k$). Gli indici restano strettamente crescenti, quindi $Z$ è una sottosequenza di $X_{i..j}$ della stessa lunghezza $k$. $Z$ è ancora antipalindroma: le coppie interne non sono cambiate, e la coppia esterna è diventata $(x_i, x_j)$, di caratteri diversi (se nessuna sostituzione è avvenuta, era già $j_1 = i$, $j_k = j$ e la coppia era $(x_i, x_j)$). Quindi $Z$ è una SALM con $z_1 = x_i$ e $z_k = x_j$. La sottostringa interna $Z_{2..k-1}$ è antipalindroma e sottosequenza di $X_{i+1..j-1}$. Se non fosse una SALM di $X_{i+1..j-1}$, con il cut-and-paste si sostituirebbe con una SALM $W$ di $X_{i+1..j-1}$: $\langle x_i, W, x_j \rangle$ sarebbe antipalindroma (le coppie interne vengono da $W$, quella esterna è $(x_i, x_j)$) e più lunga di $Z$, contraddizione.

Punto 5, $x_i = x_j$. Sia $Z'$ una SALM di $X_{i..j}$. Se $Z' = \epsilon$ la tesi è ovvia (anche le sottostringhe hanno SALM vuote). Altrimenti $z_1 \ne z_k$ per l'antipalindromia, quindi $z_1$ e $z_k$ non possono essere entrambi uguali al comune valore $x_i = x_j$. Se $z_1 \ne x_i$, l'indice $i$ non è usato ($j_1 > i$) e $Z'$ è sottosequenza di $X_{i+1..j}$; se $z_k \ne x_j$, $j_k < j$ e $Z'$ è sottosequenza di $X_{i..j-1}$. In entrambi i casi $Z'$ è antipalindroma e per cut-and-paste deve essere una SALM della sottostringa in cui vive. Siccome le SALM delle due sottostringhe sono anche sottosequenze antipalindrome di $X_{i..j}$, $Z'$ è la più lunga delle due. $\square$

(b) Ricorrenza

Sia $s(i, j) = |\text{SALM}(X_{i..j})|$, per $1 \le i \le j \le n$:

$$s(i, j) = \begin{cases} 0 & i = j \\ 2 & j = i + 1 \ \land \ x_i \ne x_j \\ 0 & j = i + 1 \ \land \ x_i = x_j \\ 2 + s(i+1, j-1) & j > i + 1 \ \land \ x_i \ne x_j \\ \max\{s(i+1, j),\ s(i, j-1)\} & j > i + 1 \ \land \ x_i = x_j \end{cases}$$

I valori sono $0$ o ottenuti con incrementi di $2$: sono tutti pari. Si vuole $s(1, n)$.

(c) Algoritmo bottom-up

Sia $\ell = j - i + 1$ la lunghezza di $X_{i..j}$. I casi base sono $\ell = 1$ e $\ell = 2$. Per $\ell \ge 3$ la cella $(i, j)$ dipende da $(i+1, j-1)$ (lunghezza $\ell - 2$) e da $(i+1, j)$ e $(i, j-1)$ (lunghezza $\ell - 1$): una scansione per diagonali di lunghezza crescente del triangolo superiore di una tabella $S[1..n, 1..n]$ è coerente con le dipendenze.

COMPUTE_SALM(X)
  n <- length(X)
  for i <- 1 to n-1 do
    S[i, i] <- 0
    if x_i != x_{i+1} then S[i, i+1] <- 2 else S[i, i+1] <- 0
  S[n, n] <- 0                            { diagonali l = 1 e l = 2 }
  for l <- 3 to n do
    for i <- 1 to n-l+1 do
      j <- i + l - 1
      if x_i != x_j then S[i, j] <- S[i+1, j-1] + 2
      else S[i, j] <- MAX(S[i+1, j], S[i, j-1])
  return S[1, n]

Correttezza. Per induzione sulla lunghezza $\ell$ della sottostringa: le diagonali $\ell = 1, 2$ contengono i valori dei casi base della ricorrenza (b); per $\ell \ge 3$ al momento in cui si calcola $S[i, j]$ le celle $S[i+1, j-1]$, $S[i+1, j]$ e $S[i, j-1]$ appartengono a diagonali di lunghezza $\ell - 2$ e $\ell - 1$, già complete e corrette per ipotesi induttiva, e l'assegnamento realizza la ricorrenza. La ricorrenza è corretta per la proprietà (a). Per $n = 1$ il primo ciclo è vuoto e si restituisce $S[1,1] = 0$. Valgono anche le scansioni "righe dalla $n$ alla $1$" e "colonne con righe decrescenti". L'algoritmo è stato verificato in Python confrontandolo con l'enumerazione di tutte le sottosequenze su $500$ stringhe casuali (alfabeti di $2$ e $3$ simboli, lunghezza fino a $10$).

Esempio. $X = abbacab$ ($n = 7$). Tabella $S[i, j]$ (triangolo superiore, la diagonale vale $0$):

Per esempio $S[2,3] = 0$ perché $x_2 = x_3 = b$; $S[3,5] = 2 + S[4,4] = 2$ ($b \ne c$); $S[2,6] = 2 + S[3,5] = 4$ ($b \ne a$); e $S[1,7] = 2 + S[2,6] = 6$ ($a \ne b$). Una SALM di lunghezza $6$ è $\langle a, b, b, c, a, b \rangle$ (coppie $(a,b), (b,a), (b,c)$ tutte diverse), sottosequenza di $abbacab$ con indici $1, 2, 3, 5, 6, 7$.

Se si vuole solo la lunghezza, come per la LPS, bastano tre vettori (la diagonale corrente e le due precedenti): spazio lineare.

(d) Numero di confronti

L'algoritmo esegue un confronto tra caratteri di $\Sigma$ per ogni sottostringa di lunghezza $\ell \ge 2$, cioè per ogni coppia $i < j$ (i MAX confrontano interi, non caratteri):

$$T(n) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} 1 = \sum_{i=1}^{n-1} (n - i) = \sum_{i'=1}^{n-1} i' = \binom{n}{2} = \frac{n(n-1)}{2} = \Theta(n^2).$$

Lo stesso risultato si ottiene per diagonali: $n - 1$ confronti sulla diagonale $\ell = 2$ (nel primo ciclo) e $n - \ell + 1$ sulla diagonale $\ell \ge 3$, in tutto $\sum_{\ell=2}^{n} (n - \ell + 1) = \sum_{k=1}^{n-1} k$. Per l'esempio $n = 7$: $21$ confronti.