No.962 LCPs

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 39
作問者 : Lemma299Lemma299 / テスター : lumc_lumc_
3 ProblemId : 3766 / 出題時の順位表
問題文最終更新日: 2019-12-24 13:19:44

問題文

一つ以上の文字列について,最大共通接頭辞 $\mathrm{LCP}(s_1, s_2, \cdots, s_K)$ を $s_1, s_2, \cdots, s_K$ すべてにとっての接頭辞であって長さが最大の文字列と定義します.

$N$ 個の英小文字からなる文字列が与えられるので,次の値を求めてください.

  • $\displaystyle{\sum_{L = 1}^{N} \sum_{R = L}^{N} |\mathrm{LCP}(S_L, S_{L + 1}, \cdots, S_R)| (R - L + 1)}$
  • ただし文字列 $T$ について $|T|$ とはその文字列の長さを表します.

入力

$N$
$S_1$
$S_2$
$\vdots$
$S_N$
  • $1 \le N \le 2 \times 10^5$
  • $1 \le |S_i| \le 2 \times 10^5$
  • $1 \le \displaystyle{\sum_i |S_i|} \le 2 \times 10^5$
  • $S_i$ は英小文字のみからなる文字列.

出力

値を整数で一行に出力してください.

サンプル

サンプル1
入力
4
akane
akari
aoi
po
出力
26

区間 [1, 1] の LCP は akane でその長さは 5 です.
区間 [1, 2] の LCP は aka でその長さは 3 です.
区間 [1, 4] の LCP は空文字列でその長さは 0 です.
答えは $(5 * 1 + 3 * 2 + 1 * 3 + 0 * 4) + (5 * 1 + 1 * 2 + 0 * 3) + (3 * 1 + 0 * 2) + (2 * 1) = 26$ です.

サンプル2
入力
5
a
a
a
a
a
出力
35

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。