Nombre de sous-chaînes distinctes dans une chaîne

Question

D'après ce que j'ai compris, la meilleure façon de la mettre en œuvre est d'utiliser le tableau de suffixe $ s $ de la chaîne $ w $ et de son array LCP (préfixe commun le plus long) $ l $.

La réponse peut être obtenue par

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

Ce que je n'obtiens pas, c'est comment et pourquoi cela fonctionne-t-il?

Je serais très reconnaissant si quelqu'un l'explique.

Answer 1

Au lieu d'une preuve formelle, je veux donner une certaine intuition derrière la formule. Le tableau de suffixe contient tous les suffixes de la chaîne $ w $. Une sous-chaîne n'est rien d'autre qu'un préfixe d'un suffixe. Donc, si vous comptez $ sum_i | s [i] | $, vous obtiendrez toutes les sous-chaînes, mais bien sûr, vous surcourez le nombre de différent Sous-8.

Regardons de plus près. Supposons les $ s [i-1] = xyz $ et $ s [i] = xyxyz $. Par la méthode de comptage ci-dessus, l'entrée $ s [i-1] $ a compté les sous-chaînes $ x, xy $ et $ xyz $ et l'entrée $ s [i] $ compté $ x, xy, xyx, xyxy, xyxyz $. Vous remarquerez que, puisque les préfixes de la longueur 2 des deux entrées sont les mêmes, nous avons doublé $ x, xy $. Mais la durée du préfixe commun le plus long est stocké en $ l [i] $, nous le soustrayons donc pour compenser la surconsie.