matriz LCP

En informática , la matriz de prefijos comunes más larga ( matriz LCP ) es una estructura de datos auxiliar de la matriz de sufijos . Almacena las longitudes de los prefijos comunes más largos (LCP) entre todos los pares de sufijos consecutivos en una matriz de sufijos ordenados.

Por ejemplo, si A  := [aab, abdominales, abaab, B, baab] es una matriz de sufijos, el prefijo común más largo entre A [1] =aaby A [2] =abdominales es aque tiene una longitud de 1, entonces H [2] = 1 en la matriz LCP H . Asimismo, el LCP de A [2] =abdominalesy A [3] =abaab es abdominales, entonces H [3] = 2.

Aumentar la matriz de sufijos con la matriz LCP permite simular eficientemente recorridos de arriba hacia abajo y de abajo hacia arriba del árbol de sufijos , ^{[1] [2]} acelera la coincidencia de patrones en la matriz de sufijos ^[3] y es un requisito previo para el sufijo comprimido árboles. ^[4]

La matriz LCP fue introducida en 1993 por Udi Manber y Gene Myers junto con la matriz de sufijos para mejorar el tiempo de ejecución de su algoritmo de búsqueda de cadenas. ^[3]

Sea la matriz de sufijos de la cadena de longitud , donde es una letra centinela que es única y lexicográficamente más pequeña que cualquier otro carácter. Deje denotar la subcadena de que van desde a . Por lo tanto, es el sufijo más pequeño de .${\ estilo de visualización A}$${\displaystyle S=s_{1},s_{2},\ldots s_{n-1}\$}$${\ estilo de visualización n}$${\ estilo de visualización \ $}$${\ estilo de visualización S [i, j]}$${\ estilo de visualización S}$${\ estilo de visualización i}$${\ estilo de visualización j}$${\displaystyle S[A[i],n]}$${\ estilo de visualización i}$${\ estilo de visualización S}$

Denote la longitud del prefijo común más largo entre dos cadenas y . Entonces, la matriz LCP es una matriz de enteros de tamaño tal que no está definido y para cada . Por lo tanto , almacena la longitud del prefijo común más largo del sufijo lexicográficamente más pequeño y su predecesor en la matriz de sufijos.${\ estilo de visualización \ nombre del operador {lcp} (v, w)}$${\ estilo de visualización v}$${\ estilo de visualización w}$${\ estilo de visualización H [1, n]}$${\ estilo de visualización n}$${\ estilo de visualización H [1]}$${\displaystyle H[i]=\operatorname {lcp} (S[A[i-1],n],S[A[i],n])}$${\ estilo de visualización 1 <i \ leq n}$${\ Displaystyle H[i]}$${\ estilo de visualización i}$

Caso 1 ( ): suponga que los sufijos , y de la cadena ya se agregaron al árbol de sufijos. Luego se agrega el sufijo al árbol como se muestra en la imagen. La ruta más a la derecha está resaltada en rojo.${\ estilo de visualización d (v) = H [i + 1]}$${\ estilo de visualización \ $}$${\displaystyle ana\$}$${\displaystyle anana\$}$${\displaystyle plátano\$}$${\displaystyle S=plátano\$}$${\displaystyle na\$}$

Caso 2 ( ): Para agregar sufijo , el borde del sufijo previamente insertado debe dividirse. El nuevo borde del nuevo nodo interno se etiqueta con el prefijo común más largo de los sufijos y . Los bordes que conectan las dos hojas están etiquetados con los caracteres de sufijo restantes que no forman parte del prefijo.${\displaystyle d(v)<H[i+1]}$${\displaystyle nana\$}$${\displaystyle na\$}$${\displaystyle na\$}$${\displaystyle nana\$}$