3502. 密码碰撞

单测试点时限: 2.0 秒

内存限制: 256 MB

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

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

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

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

换句话说,我们现在需要知道,有多少有序对 () 使得 的子串。

输入

行包含一个整数 ,表示密码表中密码的数量。
() 行包含一个长度不超过 且由小写字母组成的字符串,表示

输出

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

样例

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

提示

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

35 人解决,59 已尝试。

52 份提交通过,共有 333 份提交。

7.9 EMB 奖励。

创建: 10 月,2 周前.

修改: 10 月,1 周前.

最后提交: 1 周前.

来源: N/A

标签