Sto osservando lo pseudo-codice fornito nella figura 3 del documento originale che introduce i suffissi "SUFFIX ARRAYS: A NEW METHOD FOR ON-LINE STRING SEARCHES".Errata nel documento originale sugli array di suffissi?
Non riesco a capire la logica per le linee 4 e 5 (indicizzazione da 0). Le linee legge:
altrimenti se r < P o w r ≤ un Pos [N-1] + rpoi
L W ← N
W è lo schema di lunghezza "P" che stiamo cercando e r è lcp(A[pos[N-1]:], W). Il problema è che in quasi tutti i casi, questo lcp sarà inferiore alla lunghezza di "W". Questo condizionale ha lo scopo di gestire il caso (penso) che il modello sia lessicograficamente più grande del suffisso lessicograficamente più grande dell'array, ma non lo prova affatto. Linee 2 & 3, d'altra parte, che prova se W è minore della suffisso lexicographically piccolo sembrano perfettamente senso
se l = P o w l ≤ un Pos [0] + lpoi
L W ← 0
Credo che le linee originali dovrebbero leggere qualcosa di simile:
altrimenti se r < P e w r> un Pos [N-1 ] + rquindi
L W ← N
L'unico modo che W può essere superiore A[pos[N-1]:] è se ha un lcp più corta della lunghezza del pattern (altrimenti, tutti W partite e così W non può essere maggiore, solo minore o uguale alla cosa con cui stiamo condividendo lo lcp) E se il carattere dopo lo lcp è maggiore in W rispetto a A[pos[N-1]]. Questo sembra avere un senso? Si tratta di un errore nella carta originale? In caso contrario, qualcuno può spiegarmi come sto interpretando male il codice originale?