3502. 密码碰撞

单点时限: 2.0 sec

内存限制: 256 MB

$EOJ$ 的登录系统爆出了一个重大问题,当正确的密码是你输入的密码的子串时,就可以成功登录!

例如你的密码是 abc,则你输入 abccaabc,甚至 dfjklsdfabcsdjfkl,都可以成功登录!

出现了这么大的问题,那就一定要有人来背锅,管理员们希望在背锅之前先衡量一下锅的大小。

现在有一份 $EOJ$ 用户的密码表,里面包含了 $n$ 个用户的密码,第 $i$ 个用户的密码是 $pwd_i$。我们定义锅的大小为所有有序对 $(i, j)$ ($i \neq j$) 的数量,使得用户 $i$ 能够输入他的密码 $pwd_i$ 成功登陆用户 $j$ 的账户。

换句话说,我们现在需要知道,有多少有序对 $(i, j)$ ($i \neq j$) 使得 $pwd_j$ 是 $pwd_i$ 的子串。

输入格式

第 $1$ 行包含一个整数 $n$,$1 \leq n \leq 20~000$,表示密码表中密码的数量。
第 $1+i$ ($1 \leq i \leq n$) 行包含一个长度不超过 $10$ 且由小写字母组成的字符串,表示 $pwd_i$。

输出格式

输出一个整数,表示满足条件的有序对的对数。

样例

Input
3
aaa
aa
abb
Output
1
Input
3
x
x
xy
Output
4
Input
5
mir
mirta
ta
ir
t
Output
6

提示

人在做,天在看,哈希大法保平安。

53 人解决,84 人已尝试。

89 份提交通过,共有 493 份提交。

4.8 EMB 奖励。

创建: 2 年,6 月前.

修改: 1 年,4 月前.

最后提交: 3 月,1 周前.

来源: N/A

题目标签