Prefacio: Mi pregunta es principalmente una pregunta algorítmica, por lo que incluso si no está familiarizado con el sufijo y las matrices LCP, probablemente pueda ayudarme.

Enesta En papel se describe cómo usar eficientemente sufijo y matrices LCP para la coincidencia de patrones de cadena.

Entendí el trabajo de SA y LCP y cómo se puede mejorar el tiempo de ejecución del algoritmoO(P*log(N)) (dóndeP es la longitud del patrón yN es la longitud de la cadena) aO(P+log(N)) (Gracias a la respuesta de Chris Eelmaaaquí y los jogojapan respondenaquí)

Estaba tratando de pasar por el algoritmo de la figura 4 que explica el uso deLLcp yRLcp. Pero tengo problemas para entender cómo funciona.

El algoritmo (tomado dela fuente):

Explicación de los nombres de variables utilizados:

lcp(v,w) : Length of the longest common prefix of v and w
W = w0..wP-1 : pattern of length P
A = a0..aN-1 : the text (length N)
Pos[0..N-1] : suffix array
L_W : index (in A) of first occurrence of the matched pattern
M : middle index of current substring
L : lower bound
R : upper bound
Lcp : array of size N-2 such that Lcp[M] = lcp(A_Pos[L_M], A_pos[M]) where L_M is the lower bound of the unique interval with M in the middle
Rcp : array of size N-2 such that Rcp[M] = lcp(A_Pos[R_M], A_pos[M]) where R_M is the upper bound of the unique interval with M in the middle

Ahora quiero probar el algoritmo usando el siguiente ejemplo (en parte tomado deaquí):

 SA | LCP | Suffix entry
 -----------------------
 5  | N/A | a  
 3  | 1   | ana  
 1  | 3   | anana  
 0  | 0   | banana  
 4  | 0   | na  
 2  | 2   | nana 

A = "banana" ; N = 6
W = "ban" ; P = 3

Quiero intentar hacer coincidir una cadena, digamosban y esperaría que el algoritmo devuelva 0 comoL_W.

Así es como pasaría por el algoritmo:

l = lcp("a", "ban") = 0
r = lcp("nana", "ban") = 0
if 0 = 3 or 'b' =< 'a' then // which is NOT the case for both conditions
    L_W = 0
else if 0 < 3 or 'b' =< 'n' then // which is the case for both conditions 
    L_W = 6 // which means 'not found'
...
...

Siento que me falta algo, pero no puedo descubrir qué. También me pregunto cómo se puede usar la matriz LCP precalculada en lugar de llamarlcp(v,w).