From manzig@cli.di.unipi.it Mon May 30 11:58:26 2005
On Mon, 30 May 2005, Giulio Manzi wrote:
La propiata delle che andava usata nel compito delle parole palindrome era:
a[i]==a[2s-i]; dove s e la lunghezza della stringa
ovvero:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
C A N N A N E $ E N A N N A C $ //attenzione alla tabualzione del
testo.
es a[3]=a[2*8-3]
a[4]=a[2*8-4]
Se la parola e' palindroma le lettere in queste posizioni sono uguali .
Risposta del docente:
La proprieta' e' giusta, ma come andava sfruttata algoritmicamente?
Un suggerimento e' nelle mie dispense sul suffix tree [GI98], pag.7.
From timothy.frassi@virgilio.it Mon May 30 15:43:03 2005
Timothy Frassi, ecco la soluzione:
Un suffix tree fornisce ad esempio questa serie di soluzioni cosi'
numerate:
ananas0
nanas1
anas2
nas3
as4
s5
Queste si possono vedere come un vettore di soluzioni (indicate con
l'indice
sol) che, a loro volta, sono vettori di stringhe (indice l).
Si costruisce un nuovo vettore di stringhe contenente il testo al
contrario:
rev = sanana(Scorso dall'indice j)
A questo punto si valuta soluzione per soluzione in ordine
confrontandola
col giusto frammento di rev (quello con le stesse lettere ma al
contrario)
limitando il confronto a k lettere. Se nell'ordine le lettere sono a
due
a due le stesse per il testo normale e ribaltato abbiamo un palindromo
di
ordine k e possiamo restituire true come in ispali (versione
compitino).
ispali2 (S, k, n)
ok = true
for (sol <- 0 to n-k+1)
l <- 0
j <- n-k-sol
while ((j < n-sol) && (ok = true))
if (S[sol][l] != rev[j]) ok = false
j++
if (ok == true) return ok
return ok
Risposta del docente:
La soluzione proposta confronta comunque tutti i suffissi
nel caso pessimo, quindi ha un costo computazionale quadratico.
Nel ciclo il numero di confronti non termina comunque dopo k passi
(ma a questo si puo' facilmente ovviare).
From castel@cli.di.unipi.it Mon May 30 17:20:09 2005
Simone Castellani, ecco la soluzione:
Si costruisce un suffix tree con la stringa data, concatenata al terminatore
&PT1, concatenata alla striga ribaltata, concatenata al terminatore &PT2.
CercaPalindoma
{
Visita lineare a livello k //visita da nodi ogni volta diversi fino a livello k
{
boolean B = terminatoriDiversi(nodo, &PT1,&PT2); //procedura che
determina se i sottoalberi partenti dal nodo "nodo" hanno terminatori diversi
if (!B)
continue;
if (indiciCorretti(Lunghezza, PT1,PT2,k))
return true;
}
return false;
}
boolean indiciCorretti (int Lunghezza, int PT1, int PT2, int k)
{
int w = PT1-k; // numero di caratteri dopo la sottostringa considerata
int y = Lunghezza-w; // lunghezza del suffisso nella parte ribaltata
if (y == PT2)
reurn TRUE;
else
return FALSE;
}
Risposta del docente:
Definire cosa e' il livello k (va inteso come lunghezza delle
stringhe, invce che come numero di nodi attraversati); inoltre,
una stringa di lunghezza k potrebbe capitare a meta' di un arco,
per cui va considerato il nodo di destinazione di tale arco.
Nella funzione indiciCorretti, la sottostringa considerata e'
sempre quella che dista k dal terminatore PT1, quindi non va bene.
L'idea e' di prendere in terminatori diversi, tutti i suffissi che
partono prima di PT1 e quelli che partono dopo PT2. Mediante
un'opportuna relazione matematica (vedi [GI98], pag.7) e' possibile
stabile se c'e' un palindromo di ordine k.
From filippo@bartali.com Mon May 30 17:20:40 2005
Soluzione di FILIPPO VOLPINI:
X stringa in ingresso
|X| cardinalità di X
K lunghezza richiesta per la palindroma
costruisco una stringa W tale che: W = X@X^R$
dove:
@ e $ sono due distinti separatori che non occorrono all'interno di X
X^R è la stringa X invertita
costruzione di un suffix tree T per la stringa W
preprocessing di T in modo da rispondere in tempo costante alle chiamate di
LCA (least common ancestor), e trovare il
prefisso comune più lungo (LCP) di due qualsiasi suffissi di W
ciclo sulle j posizioni di X per trovare la prima palindroma di lunghezza K
con centro in j
lunghezza(A) restituisce la lunghezza della stringa A
S[j] estrae da T il suffisso di W di posizione j
l'algoritmo restituisce true se esiste una palindroma di lunghezza K in X
segue la funzione in pseudo-codice:
PAL(X,K) {
W = X@X^R$
T = Costruisci_suffix_tree(W)
Preprocessing(T)
foreach j in X {
if K pari
L = lunghezza( LCP( S[j] , S[2|X|+3-j] ) )
else
L = lunghezza( LCP( S[j+1] , S[2|X|+3-j] ) )
if L >= K then return true
}
return false
}
Risposta del docente:
E' corretto, come riportato in [GI98] a pag.7.
Tuttavia, non e' accettabile come soluzione in quanto usa LCA
che non abbiamo visto a lezione.
From wyje_lahi@libero.it Mon May 30 18:43:19 2005
Giuseppe Demichele, due possibili soluzioni:
Sol 1:
Per trovare una palindrome all'interno di una stringa, si puo' costruire =
semplicemente un singlo suffix tree che contenga tutti i suffissi delle =
stringa piu' tutti i suffissi della stessa rovesciata. A questo punto =
una palindrome e' definita da tutti quei nodi che hanno "figli" sia in =
avanti che indietro a partire dalla stessa posizione.
In pratica se considero la stringa ABAB il suffix tree diventa:
$
/
A-B-A-B-$
./
\
B-A-B-$
\
$
Il suffix tree del suo inverso (BABA) e'
$
/
B-A-B-A-$
./
\
A-B-A-$
\
$
Se li sovrappongo ottengo:
$ $ $
/ / / In grassetto c'e la parte di albero in comune.
A-B-A-B-$
./
\
B-A-B-$
\ \ \
$ $ A-$
A questo punto tutti i nodi in grassetto che hanno figli a destra e a =
sinistra appartengono ad una palindrome formata proprio dal nodo a =
sinistra, egli stesso e il nodo a destra.
Ora sappiamo se c'e o meno una palindrome in una stringa. Se voglio =
sapere se c'e una palindrome di dimensione k, non devo far altro che =
contare i caratteri all'interno di quegli stessi nodi (in quanto in un =
suffix tree un nodo puo' contenere piu' caratteri essendo la =
compattazione di un suffix trie).
Sol2:
Un'altra idea e' quella di considerare, come da vostro suggerimento, il =
suffix-tree con la stringa data+$1+Tr+$2 dove $i e' un carattere che non =
appartiene al testo T, Tr e' il testo rovesciato.
Questa procedura serve per verificare che la sottostringa dalla radice =
al nodo appartenga sia a T sia a Tr. Basta controllare che abbia i 2 =
terminatori diversi nelle foglie.
boolean stessaSubst(int L, int $1, int $2, int k)
{
int a = L-($1-k); // suffisso in Tr
if (a == $2)
return TRUE;
return FALSE;
}
FindPalindroma(S,k)
{
Iterator t = new Iterator(S) //itera fra tutti i nodi a livello k
while(t.hasNext())
{
if(stessoTesto(t.next(),$1,$2)) //serve per verificare che la =
sottostringa dalla radice al nodo appartenga sia a T sia a Tr. Basta =
controllare che abbia i 2 terminatori =
diversi nelle foglie
if (stessaSubst(Lunghezza, PT1,PT2,k)) //serve per verificare che la =
sottostringa considerata si riferisca alla stessa nel testo ribaltato =
(es T=abdtab Tr=batdba il primo ab si riferisce all'ultimo ba nel =
Tr)
return true;
}
return false;
}
Risposta del docente:
Soluzione 1: corretta ma puo' richiedere tempo O(n^2)
perche' tanti sono i caratteri memorizzati nei suffix trie
(infatti, compattiamo i trie ottenendo i suffix tree, ma
il confronto delle etichette, carattere per carattere,
richiede comunque O(n^2) tempo.
Soluzione 2:
Definire cosa e' il livello k (vedere i commenti dati a Castellani).
Purtroppo la soluzione proposta puo' identificare dei falsi positivi,
ovvero una sottostringa y che non e' palindroma ma che occorre sia
come y e sia come y^R (y reversa) in T. Ribaltando T, abbiamo ancora
queste due occorrenze. Per esempio, T = CABDFBAG, dove y = AB. Vanno
effettuati ulteriori controlli per scartare situazioni di questo tipo.
From liberati@cli.di.unipi.it Mon May 30 19:29:59 2005
Giuseppe Liberati, ho provato a migliorare il primo esercizio:
Procedura Find-Suffix-Tree (r,j,k).
u = root;
k = |T|;
w = 0;
for i = 1 to k do
if ( u, T[i]) = nil;
return false;
else
q = target (r, y[j]); // associa ad un arco la sottostringa
precedente(r) con quella corrente(y[j]), ottenendo quella parziale.
(j', l) = label (r, q); // associa alla sottostringa
parziale la coppia (j', l) dove j' e' l'elemento iesimo della stringa
lunga k ;e l e' la lunghezza della sottostringa q
if j+l < = k then // j+l e' la dimensione della sottostringa del
passo jesimo sommata alla dimensione della sottostringa q finora ottenuta.
return Find-Suffix-Tree ( q, j+l, k); //richiama la procedura.
n = lengthsottostringa (j', i); //lunghezza sottostringa.
while ( w < = n\2 && sottostringa(w) == sottostringa
(n-w)) // confronto se e' palindroma, scorrendo l'indice w sino alla
meta' della sottostringa e vedendo se l'indice nella prima meta' trova
lo stesso carattere presente nella seconda meta'.
w = w+1; //incremento l'indice.
if (w > n\2)
return true //la stringa e' palindrom.
else
return false
// la stringa non e' palindroma
i++; // incremento l'indice del for e continuo la ricerca.
Risposta del docente:
Il codice mi risulta incomprensibile; me lo spieghi di persona
durante l'orale.
From iardella@cli.di.unipi.it Mon May 30 20:01:13 2005
Stefano Iardella, solluzione:
Supponiamo di costruire un suffix trie (Generalizzato) ? per il testo
-T- e per il testo |T| (-T- invertito) dove supponiamo che -T- e |T|
abbiano divesri caratteri di terminazione.
In tal caso avremo indicizzato tutti i suffissi di -T- ed anche tutti
i
suffissi di |T|. Pertanto, se una palindroma di lunghezza k esiste in
-T-,
allora essa dovra' corrispondere ad un cammino comune tra uno o piu'
coppie di nodi in ? dei quali uno indica un suffisso di -T- e l'altro
indica un suffisso di |T|.
A questo punto si fa una specie di pre-processing del trie ? in modo
da
poterci "annotare", per ogni coppia (i,j), quale e' il nodo in ? che
rappresenta
l'"ultimo" predecessore (Chiamiamolo u) che il suffisso i di -T- ha in
comune
con il suffisso j di |T|. Tale fase ha complessita' lineare (O(n)),
dove n e' la
dimensione del testo, e ci permettera', successivamente, data una
coppia (i,j)
che individua due suffissi in ?, il primo in -T- ed il secondo in |T|,
di ottenere u,
in tempo costante, ("Ultimo" predecessore comune) e di conseguenza di
sapere
quale e' la stringa piu' lunga che essi hanno in comune (Tale stringa
si trovera'
sul cammino che porta al nodo u).
Il suffix trie processato puo' ora essere utilizzato per risalire, per
ogni indice
j= k e' stato restituito
allora significa
che in -T- non c'e' nessuna palindroma di lunghezza k.
Grazie al preprocessing la complessita' e' O(n).
Risposta del docente:
Quasi corretta, nel senso che rimane il problema dei falsi positivi.
Veda la mia risposta alla soluzione 2 di Demichele.