33OJ
登录 注册

#P17504. [ICPC 2026 Wuhan I] String Matching

    ID: 20232 远端评测题 5000ms 1024MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>ICPC2026省赛/邀请赛湖北

[ICPC 2026 Wuhan I] String Matching

题目描述

给定 nn 个由小写字母组成的字符串 s1,s2,⋯ ,sns_1,s_2,\cdots,s_n。保证这些字符串已按照长度非严格递增的顺序排列(即 ∣s1∣≤∣s2∣≤⋯≤∣sn∣|s_1| \le |s_2| \le \cdots \le |s_n|)。

对于任意两个不同的字符串 sis_i 和 sjs_j(满足 1≤i<j≤n1 \le i<j \le n),定义 ti,j=si+sjt_{i,j}=s_i+s_j,表示将字符串 sis_i 和 sjs_j 按顺序拼接得到的新字符串(其中 sis_i 在前,sjs_j 在后)。

我们定义一个函数 f(t)f(t),其中 tt 是一个长度为 mm 的字符串。f(t)f(t) 的值为满足以下条件的正整数 xx(0<x≤m0<x \le m)的个数:

  • 字符串 tt 的前 xx 个字符与后 xx 个字符完全相同。即 t[1:x]=t[m−x+1:m]t[1:x]=t[m-x+1:m]。

你的任务是计算出所有合法对 (i,j)(i,j) 的 f(ti,j)f(t_{i,j}) 的总和,即求:

∑1≤i<j≤nf(ti,j).\sum_{1 \le i<j \le n} f(t_{i,j}).

输入格式

输入包含多行。

第一行包含一个整数 nn(1≤n≤1061 \le n \le 10^6),表示给定的字符串总数。

接下来 nn 行,第 ii 行包含一个由小写字母组成的字符串 sis_i(1≤∣si∣≤1061 \le |s_i| \le 10^6)。

保证所有测试数据中,所有字符串的长度之和 ∑∣si∣≤106\sum |s_i| \le 10^6。

输出格式

输出一行包含一个整数,表示所有 f(ti,j)f(t_{i,j}) 的总和。

2
ak
hbcpc
1
3
aa
abaa
ababaa
9

提示

在第二组样例中,共有 n=3n=3 个字符串,我们可以组合出 33 种不同的 ti,jt_{i,j}:

  • 当 i=1,j=2i=1,j=2 时:t1,2=aaabaat_{1,2}=\mathtt{aaabaa}。满足前缀等于后缀的长度 xx 有:1,2,61,2,6。
  • 当 i=1,j=3i=1,j=3 时:t1,3=aaababaat_{1,3}=\mathtt{aaababaa}。满足前缀等于后缀的长度 xx 有:1,2,81,2,8。
  • 当 i=2,j=3i=2,j=3 时:t2,3=abaaababaat_{2,3}=\mathtt{abaaababaa}。满足前缀等于后缀的长度 xx 有:1,4,101,4,10。

最终答案为 3+3+3=93+3+3=9。