题目描述
给定 n 个由小写字母组成的字符串 s1,s2,⋯,sn。保证这些字符串已按照长度非严格递增的顺序排列(即 ∣s1∣≤∣s2∣≤⋯≤∣sn∣)。
对于任意两个不同的字符串 si 和 sj(满足 1≤i<j≤n),定义 ti,j=si+sj,表示将字符串 si 和 sj 按顺序拼接得到的新字符串(其中 si 在前,sj 在后)。
我们定义一个函数 f(t),其中 t 是一个长度为 m 的字符串。f(t) 的值为满足以下条件的正整数 x(0<x≤m)的个数:
- 字符串 t 的前 x 个字符与后 x 个字符完全相同。即 t[1:x]=t[m−x+1:m]。
你的任务是计算出所有合法对 (i,j) 的 f(ti,j) 的总和,即求:
1≤i<j≤n∑f(ti,j).
输入格式
输入包含多行。
第一行包含一个整数 n(1≤n≤106),表示给定的字符串总数。
接下来 n 行,第 i 行包含一个由小写字母组成的字符串 si(1≤∣si∣≤106)。
保证所有测试数据中,所有字符串的长度之和 ∑∣si∣≤106。
输出格式
输出一行包含一个整数,表示所有 f(ti,j) 的总和。
2
ak
hbcpc
1
3
aa
abaa
ababaa
9
提示
在第二组样例中,共有 n=3 个字符串,我们可以组合出 3 种不同的 ti,j:
- 当 i=1,j=2 时:t1,2=aaabaa。满足前缀等于后缀的长度 x 有:1,2,6。
- 当 i=1,j=3 时:t1,3=aaababaa。满足前缀等于后缀的长度 x 有:1,2,8。
- 当 i=2,j=3 时:t2,3=abaaababaa。满足前缀等于后缀的长度 x 有:1,4,10。
最终答案为 3+3+3=9。