#P18098. String Matching

String Matching

String Matching

题目描述

给定 nn 个非空小写字母字符串 s1,…,sns_1,\ldots,s_n,按长度非递减排列,即 ∣s1∣≤⋯≤∣sn∣|s_1|\le\cdots\le|s_n|。不同下标处的字符串内容可以相同。

对于字符串 tt,设其长度为 mm,定义

$$f(t)=\#\{x\mid 1\le x\le m,\ t[1..x]=t[m-x+1..m]\}.$$

也就是说,统计非空且相等的前缀与后缀长度;长度为整个字符串的情况也要计入。

对每一对下标 1≤i<j≤n1\le i<j\le n,将 sis_i 放在 sjs_j 前面拼接,得到 si+sjs_i+s_j。求

∑1≤i<j≤nf(si+sj).\sum_{1\le i<j\le n} f(s_i+s_j).

输入格式

第一行一个整数 nn。接下来 nn 行,每行一个字符串 sis_i。

输出格式

输出一行一个整数,表示所求总和。

数据范围

1≤n≤1061\le n\le10^6,1≤∣si∣≤1061\le|s_i|\le10^6,所有字符串的长度之和不超过 10610^6。所有字符都是小写英文字母,字符串按长度非递减顺序给出。

样例 1

输入

2
ak
hbcpc

输出

1

样例 2

输入

3
aa
abaa
ababaa

输出

9