matriz LCP

Para encontrar el número de ocurrencias de una cadena dada${\displaystyle P}$(longitud${\displaystyle m}$) en un texto${\displaystyle T}$(longitud${\displaystyle N}$), ^{[ 3 ]}

• Utilizamos la búsqueda binaria contra el arreglo de sufijos de${\displaystyle T}$para encontrar la posición inicial y final de todas las ocurrencias de${\displaystyle P}$.
• Para acelerar la búsqueda, utilizamos la matriz LCP, concretamente una versión especial de la matriz LCP (LCP-LR, que se describe a continuación).

El problema de usar la búsqueda binaria estándar (sin la información LCP) es que en cada uno de los${\displaystyle O(\log N)}$Se necesitaban realizar comparaciones, comparamos P con la entrada actual del arreglo de sufijos, lo que significa una comparación de cadena completa de hasta m caracteres. Por lo tanto, la complejidad es${\displaystyle O(m\log N)}$.

La matriz LCP-LR ayuda a mejorar esto a${\displaystyle O(m+\log N)}$, de la siguiente manera:

En cualquier punto durante el algoritmo de búsqueda binaria, consideramos, como de costumbre, un rango.${\displaystyle (L,\dots ,R)}$del conjunto de sufijos y su punto central${\displaystyle M}$y decidir si continuamos nuestra búsqueda en el subrango izquierdo${\displaystyle (L,\dots ,M)}$o en el subrango correcto${\displaystyle (M,\dots ,R)}$Para tomar la decisión, comparamos${\displaystyle P}$a la cuerda en${\displaystyle M}$. Si${\displaystyle P}$es idéntico a${\displaystyle M}$, nuestra búsqueda está completa. Pero si no, ya hemos comparado el primero${\displaystyle k}$personajes de${\displaystyle P}$y luego decidió si${\displaystyle P}$es lexicográficamente más pequeño o más grande que${\displaystyle M}$. Supongamos que el resultado es que${\displaystyle P}$es más grande que${\displaystyle M}$. Entonces, en el siguiente paso, consideramos${\displaystyle (M,\dots ,R)}$y un nuevo punto central${\displaystyle M'}$en el centro:

 M ...... M' ...... R | Sabemos: lcp(P,M)==k

El truco ahora es que LCP-LR se precalcula de tal manera que un${\displaystyle O(1)}$-lookup nos dice el prefijo común más largo de${\displaystyle M}$y${\displaystyle M'}$,${\displaystyle \mathrm {lcp} (M,M')}$.

Ya sabemos (del paso anterior) que${\displaystyle M}$en sí mismo tiene un prefijo de${\displaystyle k}$personajes en común con${\displaystyle P}$:${\displaystyle \mathrm {lcp} (P,M)=k}$Ahora bien, existen tres posibilidades:

• Caso 1:${\displaystyle k<\mathrm {lcp} (M,M')}$, es decir${\displaystyle P}$tiene menos caracteres de prefijo en común con M que M en común con M'. Esto significa que el carácter (k+1) de M' es el mismo que el de M, y dado que P es lexicográficamente mayor que M, también debe ser lexicográficamente mayor que M'. Por lo tanto, continuamos en la mitad derecha (M',...,R).
• Caso 2:${\displaystyle k>\mathrm {lcp} (M,M')}$, es decir${\displaystyle P}$tiene más caracteres de prefijo en común con${\displaystyle M}$que${\displaystyle M}$tiene en común con${\displaystyle M'}$. En consecuencia, si comparáramos${\displaystyle P}$a${\displaystyle M'}$, el prefijo común sería más pequeño que${\displaystyle k}$, y${\displaystyle M'}$sería lexicográficamente más grande que${\displaystyle P}$Así pues, sin hacer realmente la comparación, continuamos en la mitad izquierda.${\displaystyle (M,\dots ,M')}$.
• Caso 3:${\displaystyle k=\mathrm {lcp} (M,M')}$. Por lo tanto, M y M' son ambos idénticos con${\displaystyle P}$en el primero${\displaystyle k}$personajes. Para decidir si continuamos en la mitad izquierda o derecha, basta con comparar${\displaystyle P}$a${\displaystyle M'}$comenzando desde el${\displaystyle (k+1)}$el personaje.
• Continuamos recursivamente.

El efecto general es que ningún personaje de${\displaystyle P}$se compara con cualquier carácter del texto más de una vez (para más detalles, véase ^{[ 3 ]} ). El número total de comparaciones de caracteres está limitado por${\displaystyle m}$, por lo que la complejidad total es realmente${\displaystyle O(m+\log N)}$.

Todavía necesitamos precalcular LCP-LR para que pueda decirnos en${\displaystyle O(1)}$Calcula el tiempo del LCP entre dos entradas cualesquiera del arreglo de sufijos. Sabemos que el arreglo LCP estándar nos da el LCP de entradas consecutivas solamente, es decir${\displaystyle \mathrm {lcp} (i-1,i)}$para cualquier${\displaystyle i}$. Sin embargo,${\displaystyle M}$y${\displaystyle M'}$En la descripción anterior, las entradas no son necesariamente consecutivas.

La clave de esto es darse cuenta de que solo ciertos rangos${\displaystyle (L,\dots ,R)}$siempre ocurrirá durante la búsqueda binaria: Siempre comienza con${\displaystyle (0,\dots ,N)}$y lo divide por la mitad, y luego continúa hacia la izquierda o hacia la derecha y divide esa mitad de nuevo y así sucesivamente. Otra forma de verlo es  : cada entrada del arreglo de sufijos aparece como punto central de exactamente un rango posible durante la búsqueda binaria. Por lo tanto, hay exactamente N rangos distintos.${\displaystyle (L\dots M\dots R)}$que posiblemente pueda desempeñar un papel durante la búsqueda binaria, y basta con precalcular${\displaystyle \mathrm {lcp} (L,M)}$y${\displaystyle \mathrm {lcp} (M,R)}$para aquellos${\displaystyle N}$rangos posibles. Entonces eso es${\displaystyle 2N}$valores precalculados distintos, por lo tanto LCP-LR es${\displaystyle O(N)}$en tamaño.

Además, existe un algoritmo recursivo sencillo para calcular el${\displaystyle 2N}$valores de LCP-LR en${\displaystyle O(N)}$tiempo del arreglo LCP estándar.

En resumen:

• Es posible calcular LCP-LR en${\displaystyle O(N)}$tiempo y${\displaystyle O(2N)=O(N)}$espacio de LCP.
• El uso de LCP-LR durante la búsqueda binaria ayuda a acelerar el procedimiento de búsqueda.${\displaystyle O(M\log N)}$a${\displaystyle O(M+\log N)}$.
• Podemos usar dos búsquedas binarias para determinar el extremo izquierdo y derecho del rango de coincidencia para${\displaystyle P}$y la longitud del rango de coincidencia se corresponde con el número de ocurrencias de P.

Dado el array de sufijos${\displaystyle A}$y la matriz LCP${\displaystyle H}$de una cuerda${\displaystyle S=s_{1},s_{2},\ldots s_{n}\$}$de longitud${\displaystyle n+1}$, su árbol de sufijos${\displaystyle ST}$se puede construir en${\displaystyle O(n)}$tiempo basado en la siguiente idea: comenzar con el árbol de sufijos parcial para el sufijo lexicográficamente más pequeño e insertar repetidamente los otros sufijos en el orden dado por la matriz de sufijos.

Dejar${\displaystyle ST_{i}}$sea ​​el árbol de sufijos parciales para${\displaystyle 0\leq i\leq n}$. Además, deja${\displaystyle d(v)}$sea ​​la longitud de la concatenación de todas las etiquetas de ruta desde la raíz de${\displaystyle ST_{i}}$al nodo${\displaystyle v}$.

Comience con${\displaystyle ST_{0}}$, el árbol que consta únicamente de la raíz. Para insertar${\displaystyle A[i+1]}$en${\displaystyle ST_{i}}$, suba por el sendero de la derecha comenzando en la hoja recién insertada${\displaystyle A[i]}$hasta la raíz, hasta el nodo más profundo${\displaystyle v}$con${\displaystyle d(v)\leq H[i+1]}$se alcanza.

Necesitamos distinguir dos casos:

• ${\displaystyle d(v)=H[i+1]}$: Esto significa que la concatenación de las etiquetas en la raíz-a-${\displaystyle v}$El camino es igual al prefijo común más largo de los sufijos.${\displaystyle A[i]}$y${\displaystyle A[i+1]}$En este caso, inserte${\displaystyle A[i+1]}$como una nueva hoja${\displaystyle x}$del nodo${\displaystyle v}$y etiquetar el borde${\displaystyle (v,x)}$con${\displaystyle S[A[i+1]+H[i+1],n]}$. Por lo tanto, la etiqueta del borde consta de los caracteres restantes del sufijo${\displaystyle A[i+1]}$que no estén ya representadas por la concatenación de las etiquetas de la raíz a${\displaystyle v}$ruta. Esto crea el árbol de sufijos parciales.${\displaystyle ST_{i+1}}$.

  

• ${\displaystyle d(v)<H[i+1]}$: Esto significa que la concatenación de las etiquetas en la raíz-a-${\displaystyle v}$La ruta muestra menos caracteres que el prefijo común más largo de sufijos.${\displaystyle A[i]}$y${\displaystyle A[i+1]}$y los caracteres faltantes están contenidos en la etiqueta del borde de${\displaystyle v}$borde más a la derecha . Por lo tanto, tenemos que dividir ese borde de la siguiente manera: Sea${\displaystyle w}$ser hijo de${\displaystyle v}$en${\displaystyle ST_{i}}$su camino más a la derecha.

1. Eliminar el borde${\displaystyle (v,w)}$.
2. Agregar un nuevo nodo interno${\displaystyle y}$y un nuevo borde${\displaystyle (v,y)}$con etiqueta${\displaystyle S[A[i]+d(v),A[i]+H[i+1]-1]}$. La nueva etiqueta consta de los caracteres faltantes del prefijo común más largo de${\displaystyle A[i]}$y${\displaystyle A[i+1]}$. Por lo tanto, la concatenación de las etiquetas de la raíz a${\displaystyle y}$La ruta ahora muestra el prefijo común más largo de${\displaystyle A[i]}$y${\displaystyle A[i+1]}$.
3. Conectar${\displaystyle w}$al nodo interno recién creado${\displaystyle y}$por un borde${\displaystyle (y,w)}$que está etiquetado${\displaystyle S[A[i]+H[i+1],A[i]+d(w)-1]}$La nueva etiqueta consta de los caracteres restantes del borde eliminado .${\displaystyle (v,w)}$que no se utilizaron como etiqueta de borde${\displaystyle (v,y)}$.
4. Agregar${\displaystyle A[i+1]}$como una nueva hoja${\displaystyle x}$y conectarlo al nuevo nodo interno${\displaystyle y}$por un borde${\displaystyle (y,x)}$que está etiquetado${\displaystyle S[A[i+1]+H[i+1],n]}$. Por lo tanto, la etiqueta del borde consta de los caracteres restantes del sufijo${\displaystyle A[i+1]}$que no estén ya representadas por la concatenación de las etiquetas de la raíz a${\displaystyle v}$camino.
5. Esto crea el árbol de sufijos parciales.${\displaystyle ST_{i+1}}$.

Un argumento de amortización simple muestra que el tiempo de ejecución de este algoritmo está acotado por${\displaystyle O(n)}$:

Los nodos que se recorren en el paso${\displaystyle i}$subiendo por el sendero más a la derecha de${\displaystyle ST_{i}}$(aparte del último nodo)${\displaystyle v}$) se eliminan del camino más a la derecha , cuando${\displaystyle A[i+1]}$se agrega al árbol como una nueva hoja. Estos nodos nunca se volverán a recorrer en todos los pasos subsiguientes.${\displaystyle j>i}$Por lo tanto, como máximo${\displaystyle 2n}$Se recorrerán todos los nodos.

La matriz LCP${\displaystyle H}$solo contiene la longitud del prefijo común más largo de cada par de sufijos consecutivos en la matriz de sufijos${\displaystyle A}$Sin embargo, con la ayuda de la matriz de sufijos inversos${\displaystyle A^{-1}}$(${\displaystyle A[i]=j\Leftrightarrow A^{-1}[j]=i}$, es decir, el sufijo${\displaystyle S[j,n]}$que comienza en la posición${\displaystyle j}$en${\displaystyle S}$se almacena en posición${\displaystyle A^{-1}[j]}$en${\displaystyle A}$) y consultas mínimas de rango de tiempo constante en${\displaystyle H}$, es posible determinar la longitud del prefijo común más largo de sufijos arbitrarios en${\displaystyle O(1)}$tiempo.

Debido al orden lexicográfico de la matriz de sufijos, cada prefijo común de los sufijos${\displaystyle S[i,n]}$y${\displaystyle S[j,n]}$tiene que ser un prefijo común de todos los sufijos entre${\displaystyle i}$posición de en el array de sufijos${\displaystyle A^{-1}[i]}$y${\displaystyle j}$posición de en el array de sufijos${\displaystyle A^{-1}[j]}$Por lo tanto, la longitud del prefijo más largo que comparten todos estos sufijos es el valor mínimo en el intervalo${\displaystyle H[A^{-1}[i]+1,A^{-1}[j]]}$Este valor se puede encontrar en tiempo constante si${\displaystyle H}$Se preprocesa para consultas de rango mínimo.

Así, dada una cadena${\displaystyle S}$de longitud${\displaystyle n}$ y dos posiciones arbitrarias ${\displaystyle i,j}$en la cadena${\displaystyle S}$ con${\displaystyle A^{-1}[i]<A^{-1}[j]}$, la longitud del prefijo común más largo de los sufijos${\displaystyle S[i,n]}$y${\displaystyle S[j,n]}$se puede calcular de la siguiente manera:${\displaystyle \operatorname {LCP} (i,j)=H[\operatorname {RMQ} _{H}(A^{-1}[i]+1,A^{-1}[j])]}$.