68. 計算前綴

0 Judge

Code: 0


計算前綴

題目敘述

$\DeclareMathOperator{\LCP}{LCP}$ 有 $n$ 個小寫字串 $s_0, s_1, \cdots, s_{n - 1}$,試計算 $\sum_{i = 0}^{n - 1} \sum_{j = 0}^{n - 1} \LCP(s_i, s_j)^2$

$\LCP(s, t)$ 是 $s, t$ 的最長共同前綴

$$ 1 \leq |s_i|$$ $$\sum_{i = 0}^{n - 1} |s_i| \leq 10^5 $$

字串可能重複

輸入

每筆測資只有一個輸入 第一行有一個數字 $n$ 接下來 $n$ 行,每行有一個字串 $s_j$

輸出

一個數字 $\sum_{i = 0}^{n - 1} \sum_{j = 0}^{n - 1} \LCP(s_i, s_j)^2$

Sample Input

10
bbbababaab
bababbaaba
aaaaababaa
abbbababbb
aaabbbbbaa
babaaaabbb
bbabbbbabb
baaabaabaa
baabbbaaab
bbabaabbba

Sample Output

1176

Sample Input

2
aaaaaaaaaaaa
ptt

Sample Output

153

Hint

附上簡單 Trie 實作

https://gist.github.com/rareone/798e1bf73d025d64a74c7b06096bf8bb


Judge Setting

run-time limit: 1000 ms
memory limit: 67108864 byte
測資數量: 24