Número de subcadenas distintas en una cadena

Question

Por lo que he llegado a entender, la mejor manera de implementarlo es usar la matriz de sufijo $ s $ de la cadena $ w $ y su lcp-array (prefijo común más largo) $ l $.

La respuesta se puede obtener por

$$ sum_ {i = 1}^{| w |} izquierda (| s [i] | -l [i -1] right). $$

Lo que no entiendo es cómo y por qué está funcionando esto?

Estaría muy agradecido si alguien explicara esto.

Answer 1

En lugar de una prueba formal, quiero dar alguna intuición detrás de la fórmula. La matriz de sufijo contiene todos los sufijos de la cadena $ W $. Una subcadena no es más que un prefijo de un sufijo. Entonces, si cuenta $ sum_i | s [i] | $, obtendrá todas las subcadenas, pero por supuesto que supera el número de diferente subcadenas.

Echemos un vistazo más de cerca. Suponga el $ S [i-1] = xyz $ y $ s [i] = xyxyz $. Según el método de conteo anterior, la entrada $ S [I-1] $ contó las subcadenas $ x, xy $ y $ xyz $ y la entrada $ s [i] $ contó $ x, xy, xyx, xyxy, xyxyz $. Notará que, dado que los prefijos de longitud 2 de ambas entradas son las mismas, hemos contado $ X, XY $. Pero la longitud del prefijo común más largo se almacena en $ l [i] $, por lo que la restamos para compensar el sobrealimentación.