E - Yet Another Sigma Problem 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

文字列 x,y に対して f(x,y) を以下で定義します。

  • x,y の最長共通接頭辞の長さを f(x,y) とする。

英小文字からなる N 個の文字列 (S_1,\ldots,S_N) が与えられます。次の式の値を求めてください。

\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(S_i,S_j)


制約

  • 2\leq N\leq 3\times 10^5
  • S_i は英小文字からなる文字列
  • 1\leq |S_i|
  • |S_1|+|S_2|+\ldots+|S_N|\leq 3\times 10^5
  • 入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N 
S_1 \ldots S_N

出力

答えを出力せよ。

入力例 1

3
ab abc arc

出力例 1

4
  • f(S_1,S_2)=2
  • f(S_1,S_3)=1
  • f(S_2,S_3)=1

なので、答えは f(S_1,S_2)+f(S_1,S_3)+f(S_2,S_3) = 4 です。

入力例 2

11
ab bb aaa bba baba babb aaaba aabbb a a b

出力例 2

32

Score: 500 points

Problem Statement

For strings x and y, define f(x, y) as follows:

  • f(x, y) is the length of the longest common prefix of x and y.

You are given N strings (S_1, \ldots, S_N) consisting of lowercase English letters. Find the value of the following expression:

\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(S_i,S_j).


Constraints

  • 2 \leq N \leq 3\times 10^5
  • S_i is a string consisting of lowercase English letters.
  • 1 \leq |S_i|
  • |S_1|+|S_2|+\ldots+|S_N|\leq 3\times 10^5
  • All input numbers are integers.

Input

The input is given from Standard Input in the following format:

N 
S_1 \ldots S_N

Output

Print the answer.

Sample Input 1

3
ab abc arc

Sample Output 1

4
  • f(S_1,S_2)=2
  • f(S_1,S_3)=1
  • f(S_2,S_3)=1

Thus, the answer is f(S_1,S_2) + f(S_1,S_3) + f(S_2,S_3) = 4.

Sample Input 2

11
ab bb aaa bba baba babb aaaba aabbb a a b

Sample Output 2

32