Anzahl der unterschiedlichen Substrings in einer Zeichenfolge

Question

Nach dem, was ich verstanden habe, ist der beste Weg, um das Suffix-Array $ s $ des String $ W $ und das LCP-Array (längste gemeinsame Präfix) $ l $ zu verwenden.

Die Antwort kann durch erhalten werden durch

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

Was ich nicht bekomme, ist, wie und warum funktioniert das?

Ich wäre sehr dankbar, wenn jemand das erklären würde.

Answer 1

Anstelle eines formellen Beweises möchte ich eine gewisse Intuition hinter der Formel geben. Das Suffix -Array enthält alle Suffixe der String $ W $. Ein Substring ist nichts anderes als ein Präfix eines Suffix. Wenn Sie also $ sum_i | s [i] | $ zählen, erhalten Sie alle Substrings, aber natürlich übertrieben Sie die Anzahl der Anzahl von anders Substrings.

Schauen wir uns genauer an. Angenommen, $ s [i-1] = xyz $ und $ s [i] = xyxyz $. Nach der obigen Zählmethode zählte der Eintrag $ S [i-1] $ die Substrings $ x, xy $ und $ xyz $ und der Eintrag $ s [i] $ zähl $ x, xy, xyx, xyxy, xyxyz $. Sie werden feststellen, dass die Präfixe von Länge 2 beider Einträge gleich sind, haben wir doppelt gezählt $ x, xy $. Aber die Länge des längsten gemeinsamen Präfixes wird in $ l [i] $ gespeichert, also subtrahieren wir sie, um die Überbesprechung auszugleichen.