No.962 LCPs
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 50
作問者 :
polylogK
/ テスター :
lumc_
タグ : / 解いたユーザー数 50
作問者 :
polylogK
/ テスター :
lumc_
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。