Algoritmo di Baeza-Yates e Gonnet

Con questo algoritmo si ha il preprocessing del pattern $P$ di lunghezza $m$ in tempo $\Theta(|\Sigma|+m)$. Questo pre-processamento avviene tramite il calcolo di una tabella $B$ di $|\Sigma|$ words di bit $B_\sigma$, ognuna di lunghezza $m$. La scansione del testo $T$ di lunghezza $n$ è in $\Theta(n)$.

Si sfrutta il paradigma shift-and (esatto) confrontando quindi delle word binarie e non dei simboli.

Le operazioni effettuabili sulle word sono le solite

• AND
• OR
• RSHIFT
• RSHIFT1

Si ha quindi che ogni word $B_\sigma$ è una word di $m$ bit $\{0, 1\}$:

$$ B_\sigma = b_!b_2...b_m $$

tale che:

$$ b_i = B_\sigma[i] = 1 \iff P[i] = \sigma $$

• Esempio di tabella $B$

La tabella prodotta $B$ è quindi l’insieme delle word $B_\sigma$, $\forall \sigma \in \Sigma$.

In pratica ho la tabella con un numero di righe pari al numero di simboli. In ogni riga ho una word dove a 1 ho solo gli elementi corrispondenti al carattere della riga nel pattern.

Si ha quindi il procedimento di calcolo:

1. tutte le word di $B_\sigma$ sono inizializzate a bit di soli 0
2. si inizializza una maschera $M$, che è una word di $m$ bit tutti uguali a 0 tranne il più significativo che è pari a 1
3. si esegue una scansione di $P$ da sinistra verso destra, e per ogni posizione $i$ faccio:
   • $B_{P[i]} = M \text{ OR } B_{P[i]}$
   • $M = \text{RSHIFT}(M)$