Prefix or Suffix

2 secs 1024 MB

文字列 $T$ のスコアは $2|T| - (T の先頭\ k\ 文字と末尾\ k\ 文字が一致するような\ k\ の数)$ です。 $2|T|$ の総和は $T$ の長さごとに求めると容易です。もう一つの項を考えます。

$S$ のある同じ長さの部分文字列の先頭 $k$ 文字と末尾 $k$ 文字のペアは、 $S$ のある同じ長さの部分文字列のペアと対応します。また、 $S$ の同じ長さの部分文字列 $S_i S_{i+1} \dots S_{i+l-1}$ と $S_j S_{j+1} \dots S_{j+l-1}$ のペアは文字列 $S_i S_{i+1} \dots S_{j+l-1}$ の先頭 $l$ 文字と末尾 $l$ 文字のペアと対応します。したがって、 $S_i S_{i+1} \dots S_{i+l-1}$ と $S_j S_{j+1} \dots S_{j+l-1}$ が一致するような $(i,j,l)(i \le j)$ の組の数を求めればよいです。

$(i,j)$ が一致するものをまとめて数えることにします。ある $(i,j)$ について、条件を満たす $l$ の数は文字列 $S_i S_{i+1} \dots S_{N}$ と $S_j S_{j+1} \dots S_{N}$ の Longest Common Prefixの長さと一致します。 $i=j$ を満たす組についての総和は容易に求められます。 $i<j$ を満たす組については、文字列 $S$ のLCP Arrayのある区間と対応します。したがって、LCP Array の全ての区間について最小値を求め、それらの総和を求めればよいです。これについてはstd::setやstackを用いて各値が最小値となる区間を求めると高速に解くことができます。詳しくは https://atcoder.jp/contests/agc005/tasks/agc005_b の解説を参照してください。

時間計算量は $O(N \log N)$ で十分高速です。Suffix Arrayの構築にSA-ISを、区間最小値の総和を求めるのにstackを利用した場合は $O(N)$ となります。