/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
リマクは、文字列の先頭 2 文字のうち片方を取り除くことを繰り返し行えます。例えば、abcxyx \rightarrow acxyx \rightarrow cxyx \rightarrow cyx とすることができます。
N 個の相異なる文字列 S_1, S_2, \ldots, S_N が与えられます。N \cdot (N-1) / 2 個のペア (S_i, S_j) のうち何個において、リマクは一方からもう一方を得ることができるでしょうか。
制約
- 2 \leq N \leq 200\,000
- S_i は英小文字
a-zからなる。 - S_i \neq S_j
- 1 \leq |S_i|
- |S_1| + |S_2| + \ldots + |S_N| \leq 10^6
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
リマクが一方の文字列からもう一方を得られるような非順序対 (S_i, S_j) (i \neq j) の個数を出力せよ。
入力例 1
3 abcxyx cyx abc
出力例 1
1
条件を満たすペアは (abcxyx, cyx) のみです。
入力例 2
6 b a abc c d ab
出力例 2
5
条件を満たすペアは (b, abc), (a, abc), (abc, c), (b, ab), (a, ab) の 5 個です。
Score : 700 points
Problem Statement
Limak can repeatedly remove one of the first two characters of a string, for example abcxyx \rightarrow acxyx \rightarrow cxyx \rightarrow cyx.
You are given N different strings S_1, S_2, \ldots, S_N. Among N \cdot (N-1) / 2 pairs (S_i, S_j), in how many pairs could Limak obtain one string from the other?
Constraints
- 2 \leq N \leq 200\,000
- S_i consists of lowercase English letters
a-z. - S_i \neq S_j
- 1 \leq |S_i|
- |S_1| + |S_2| + \ldots + |S_N| \leq 10^6
Input
Input is given from Standard Input in the following format.
N S_1 S_2 \vdots S_N
Output
Print the number of unordered pairs (S_i, S_j) where i \neq j and Limak can obtain one string from the other.
Sample Input 1
3 abcxyx cyx abc
Sample Output 1
1
The only good pair is (abcxyx, cyx).
Sample Input 2
6 b a abc c d ab
Sample Output 2
5
There are five good pairs: (b, abc), (a, abc), (abc, c), (b, ab), (a, ab).