Exam

题意翻译

给定互不相同的字符串 $s_1, s_2, \cdots, s_n$，求有多少对 $(i, j)$ 满足： - $i \neq j$ - $s_j$ 是 $s_i$ 的子串。 - 不存在 $k$ $(k \neq i, k \neq j)$ 满足 $s_j$ 是 $s_k$ 的子串且 $s_k$ 是 $s_i$ 的子串。 保证 $n,\sum \lvert s_i \rvert \leq 10^6$。 我们规定 $a$ 是 $b$ 的字串仅当通过将 $b$ 从前和后删除若干个（当然可以是零个或所有）字符可以得到 $a$。 对于样例一，$(1,2),(3,5),(5,4)$ 满足要求。 对于样例二，$(1,2),(1,3),(2,4),(3,4)$ 满足要求。

题目描述

This year a Chunin Selection Exam is held again in Konoha, and taking part in it are $ n $ ninjas named $ s_1 $ , $ s_2 $ , ..., $ s_n $ . All names are distinct. One of the exam stages consists of fights between the participants. This year the rules determining the ninjas for each fight are the following: ninjas $ i $ and $ j $ fight against each other if the following conditions are held: - $ i \neq j $ ; - $ s_{j} $ is a substring of $ s_{i} $ ; - there is no $ k $ except $ i $ and $ j $ that $ s_{j} $ is a substring of $ s_{k} $ , and $ s_{k} $ is a substring of $ s_{i} $ . A string $ a $ is a substring of a string $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end. Your task is to find out how many fights are going to take place this year.

输入输出格式

输入格式

The first line consists of the only integer $ n $ ( $ 1 \leq n \leq 10^{6} $ ) standing for the number of examinees. The following $ n $ lines contain their names. No two names coincide, all names are non-empty and consist of lowercase English letters. The total length of all names doesn't exceed $ 10^6 $ .

输出格式

Print the only integer standing for the number of fights.

输入输出样例

输入样例 #1

5
hidan
dan
hanabi
bi
nabi

输出样例 #1

3

输入样例 #2

4
abacaba
abaca
acaba
aca

输出样例 #2

4

说明

In the first example hidan fights against dan, and hanabi fights against nabi, who also fights bi. Ninjas named hanabi and bi don't fight each other since there is the ninja called nabi who breaks the third condition for them. In the second example the fights are held between abacaba and acaba, abacaba and abaca, acaba and aca, abaca and aca.

题意翻译

给定互不相同的字符串 $s_1, s_2, \cdots, s_n$，求有多少对 $(i, j)$ 满足： - $i \neq j$ - $s_j$ 是 $s_i$ 的子串。 - 不存在 $k$ $(k \neq i, k \neq j)$ 满足 $s_j$ 是 $s_k$ 的子串且 $s_k$ 是 $s_i$ 的子串。 保证 $n,\sum \lvert s_i \rvert \leq 10^6$。 我们规定 $a$ 是 $b$ 的字串仅当通过将 $b$ 从前和后删除若干个（当然可以是零个或所有）字符可以得到 $a$。 对于样例一，$(1,2),(3,5),(5,4)$ 满足要求。 对于样例二，$(1,2),(1,3),(2,4),(3,4)$ 满足要求。