#P18098. String Matching
String Matching
String Matching
题目描述
给定 个非空小写字母字符串 ,按长度非递减排列,即 。不同下标处的字符串内容可以相同。
对于字符串 ,设其长度为 ,定义
$$f(t)=\#\{x\mid 1\le x\le m,\ t[1..x]=t[m-x+1..m]\}.$$也就是说,统计非空且相等的前缀与后缀长度;长度为整个字符串的情况也要计入。
对每一对下标 ,将 放在 前面拼接,得到 。求
输入格式
第一行一个整数 。接下来 行,每行一个字符串 。
输出格式
输出一行一个整数,表示所求总和。
数据范围
,,所有字符串的长度之和不超过 。所有字符都是小写英文字母,字符串按长度非递减顺序给出。
样例 1
输入
2
ak
hbcpc
输出
1
样例 2
输入
3
aa
abaa
ababaa
输出
9