Arreglo de prefijo común más largo

Question

A continuación se muestra la información Suffix array y LCP array para la cadena MISSISSIPPI. Sé que LCP da información sobre la duración del prefijo común más largo entre str[i - 1] y str[i]. ¿Cómo obtengo la longitud de prefijo común más larga entre dos sufijos arbitrarios de esta cadena? Por ejemplo, quiero prefijo más largo común entre MISSISSIPPI y ISSIPPI

SA LCP 
12 0  $ 
11 0  I$ 
8 1  IPPI$ 
5 1  ISSIPPI$ 
2 4  ISSISSIPPI$ 
1 0  MISSISSIPPI$ 
10 0  PI$ 
9 1  PPI$ 
7 0  SIPPI$ 
4 2  SISSIPPI$ 
6 1  SSIPPI$ 
3 3  SSISSIPPI$ 

Answer 1

De http://en.wikipedia.org/wiki/Suffix_array, tenemos que "El hecho de que el valor mínimo LCP que pertenece a una serie consecutiva de sufijos ordenados da el prefijo común más larga entre todos los los sufijos también pueden ser útiles ". Entonces en su caso, el LCP entre MISSISSIPPI e ISSIPPI es mínimo (4, 0) = 0.

Puede encontrar el mínimo en un rango en el tiempo O (1) a través de http://en.wikipedia.org/wiki/Range_Minimum_Query, y hay mucha información sobre enfoques alternativos si miras el enlace de TopCoder allí.