Esercizio 3

Data una stringa P (pattern) di lunghezza m e una stringa T (testo) di lunghezza n,definite su di un alfabeto , modificare il programma dell’esercizio 1cercando di sfruttare in maniera efficiente la funzione LAST_OCCURRENCEcalcolata per il pattern P (esercizio 2). Incrementare un contatore C ogni volta cheviene effettuato un confronto tra caratteri di P e di T, e stampare C alla fine.

Esempi di suggerimento

Esempio 1:

STEP DI ITERAZIONE al passo i

T agtgctaaatgcggatagtaggtggatagcggggggatacP ataaaagg

Esiste un mismatch tra il carattere ‘t’ su T e il carattere ‘a’ in posizione 5 su P. Dallafunzione LAST_OCCURRENCE di P ricavo che l’occorrenza di ‘t’ più a destraè in posizione 2 (in azzurro). Quindi è certo che tra ‘t’ (in azzurro) e ‘a’ di mismatch nonesistono su P altri caratteri ‘t’. Di conseguenza posso addirittura shiftare P verso destradi 3 (=5-2) posizioni (e non di una sola, come avrebbe fatto l’algoritmo “ingenuo”dell’esercizio 1)

mismatch!

Esempio 1:

SHIFT di P verso destra di 3 (=5-2) posizioni i=i+3

prima dello shift di 3 posizioniT agtgctaaatgcggatagtaggtggatagcggggggatacP ataaaagg

i=i+3T agtgctaaatgcggatagtaggtggatagcggggggatacP ataaaagg

shift di 3 posizioni verso destra

Esempio 2:

STEP DI ITERAZIONE al passo i

T agtgctaaatgcggatagcacgtggatagcggggggatacP acaaaacg

Esiste un mismatch tra il carattere ‘c’ su T e il carattere ‘a’ in posizione 5 su P. Dallafunzione LAST_OCCURRENCE di P ricavo che l’occorrenza di ‘c’ più a destra è inposizione 7 (in azzurro). Dal momento che ‘c’ in azzurro sta a destra di ‘a’ di mismatch,non sono in grado di affermare per certo se a sinistra di ‘a’ esistono (e dove) altricaratteri ‘c’.In tale caso non posso fare altro che shiftare P verso destra di una sola posizione(come avrebbe fatto l’algoritmo “ingenuo”) se non voglio correre il rischio di perdereoccorrenze di P su T.

mismatch!

Esempio 3:

STEP DI ITERAZIONE al passo i

T agtgctaaatgcggatagtacgtggatagcggggggatacP agaaaacg

Esiste un mismatch tra il carattere ‘t’ su T e il carattere ‘a’ in posizione 5 su P. Dallafunzione LAST_OCCURRENCE di P ricaverò che ‘t’ non occorre in P (talefunzione restituirà infatti 0).In questo caso posso addirittura shiftare P verso destra di 5 (=5-0) posizionisenza correre il rischio di perdere occorrenze di P su T.

mismatch!

Esempio 3:

SHIFT di P verso destra di 5 (=5-0) posizioni i=i+5

prima dello shift di 5 posizioniT agtgctaaatgcggatagtacgtggatagcggggggatacP agaaaacg

i=i+5T agtgctaaatgcggatagtacgtggatagcggggggatacP agaaaacg

shift di 5 posizioni verso destra