文字列内の異なるサブストリングの数

Question

私が理解するようになったことから、それを実装する最良の方法は、文字列$ w $の接尾辞アレイ$ s $とそのlcp-array（最も長い一般的なプレフィックス）$ l $を使用することです。

答えはによって取得できます

$$ sum_ {i = 1}^{| w |} left（| s [i] | -l [i -1] right）。$$

私が得ていないのは、どのように、そしてなぜこれが機能するのですか？

誰かがこれを説明したらとても感謝しています。

Answer 1

正式な証拠の代わりに、式の背後にある直感を与えたいと思います。接尾辞アレイには、文字列$ w $のすべての接尾辞が含まれています。サブストリングは、接尾辞の接頭辞に他なりません。したがって、$ sum_i | s [i] | $をカウントすると、すべてのサブストリングを取得しますが、もちろんの数を過剰にカウントします 違う サブストリング。

よく見てみましょう。 $ s [i-1] = xyz $ and $ s [i] = xyxyz $を仮定します。上記のカウント方法により、エントリ$ s [i-1] $は、サブストリングス$ x、xy $および$ xyz $とエントリ$ s [i] $ $ x、xy、xyx、xyxy、xyxyz $をカウントしました。両方のエントリの長さ2のプレフィックスが同じであるため、$ x、xy $を2倍にカウントしたことがわかります。ただし、最も長い一般的なプレフィックスの長さは$ l [i] $に保存されているため、それを減算して過剰カウントを補正します。