Modifica: ho trovato la pubblicazione originale . Mi sembra che l'originale non abbia un l′(i)
. Ma potrei sbagliarmi perché la definizione di rpr(i)
è così oscura per me. Non sono sicuro di come ci si avvale quando rpr(i)
è negativo e cosa accade quando non viene trovata una tale ripetizione.
Sto cercando di implementare l'algoritmo di Boyer-Moore in base a questo . Non sono sicuro se faccia parte di un libro o se siano solo alcune note universitarie. Secondo questo (poco prima Theorem 0.2.4 ):
Definition: Let
l′(i)
denote the length of the largest suffix ofP[i..n]
that is also a prefix ofP
, if one exists. If none exists, then letl′(i)
be zero.
E poi continua da qualche altra parte con:
If, during the search stage, a mismatch occurs at position
i − 1
ofP
andL′(i) > 0
, then the good suffix rule shiftsP
byn − L′(i)
places to the right, so that theL′(i) - length
prefix of the shifted P aligns with theL′(i) - length
suffix of the unshiftedP
. In the case thatL′(i) = 0
, the good suffix rule shiftsP
byn − l′(i)
places.Note that the rules work correctly even when
l′(i) = 0
.
Fai attenzione che gli indici sono basati su 1.
La parte con cui ho problemi è grassetto . Ad esempio se abbiamo il pattern abcde
per cui l′(5) = 0
e se testiamo questo contro abcze
; la prima mancata corrispondenza si verifica in d
rispetto a z
. Ora che l′(5)
è 0
, dobbiamo spostarlo n - l′(5)
caratteri a destra e quindi abbiamo perso la possibilità di trovare la corrispondenza.
Modifica: SBAGLIATO. Dovrebbe davvero spostare n - l′(5)
caratteri perché non c'è z
o e
nel modello prima del carattere che stiamo controllando.
Quindi mi chiedo se mi manca qualcosa o no. Devo ignorare l′(i)
quando è zero?