AtCoder Library Practice Contest I - Number of Substrings

お題箱より。

解法

※この問題における文字列 $S$ の部分文字列とは、 $S$ の連続な部分を取り出した文字列であることに注意してください。慣習的に、「部分列」と書くと連続とは限らない取り出し方、「部分文字列」と書くと連続な取り出し方を指すことが多いです。意味不明ですね。

「相異なる部分文字列の個数」を求めるために、全ての部分文字列の取り方（左端と右端のインデックスの選び方）から、文字列として重複している分の個数を引くことを考えます。

ここで全ての部分文字列の取り方は、「全ての接尾辞を考えて、それぞれについて全ての接頭辞を考える」ことで列挙できます。そして「接尾辞同士の接頭辞がどの程度共通しているか」ということを考えるのにうってつけの手法が存在します。全ての接尾辞を辞書順ソートした結果を示す接尾辞配列（Suffix Array）と、このソート順において隣り合う接尾辞同士の最長共通接頭辞（Longest Common Prefix）の長さを示すLCP配列というものを使います。

これらを求めるアルゴリズム自体は蟻本や様々な記事で解説されているので省略しますが、一例として acabaca という文字列について計算した接尾辞配列とLCP配列を図に示します。AtCoder Libraryの仕様に合わせ、長さ $N$ の文字列の接尾辞配列の長さは $N$ 、LCP配列の長さは $N-1$ となるよう定義しています。

f:id:betrue12:20200909124851p:plain

このように接尾辞を辞書順ソートしてから共通接頭辞を考えることの利点は、接頭辞が長く共通しているような接尾辞同士が近くに集まることです。具体的には、ソート順で $l$ 番目と $r$ 番目の接尾辞の先頭 $k$ 文字が一致している場合、間に存在する $l, l+1, ..., r-1, r$ 番目の全ての接尾辞において先頭 $k$ 文字が一致します。

この性質を頭に入れて、重複している「接尾辞の接頭辞」の個数を数えましょう。接尾辞配列において前にあるものから見ていって、今見ている接尾辞と1つ前の接尾辞の間の最長共通接頭辞が $k$ 文字であったとします。すると今見ている接尾辞が持つ接頭辞のうち $k$ 文字以下であるものは全て登場済みです。そして逆に $k+1$ 文字以上のものは全て未登場であるということも言えます。先ほど確認した性質から、1つ前のものと一致していないのにそれよりも前のものと一致することはあり得ないからです。