P17504 [ICPC 2026 Wuhan I] String Matching

给定 $n$ 个由小写字母组成的字符串 $s_1,s_2,\cdots,s_n$。保证这些字符串已按照长度非严格递增的顺序排列（即 $|s_1| \le |s_2| \le \cdots \le |s_n|$）。 对于任意两个不同的字符串 $s_i$ 和 $s_j$（满足 $1 \le i

输入包含多行。 第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示给定的字符串总数。 接下来 $n$ 行，第 $i$ 行包含一个由小写字母组成的字符串 $s_i$（$1 \le |s_i| \le 10^6$）。 保证所有测试数据中，所有字符串的长度之和 $\sum |s_i| \le 10^6$。

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

在第二组样例中，共有 $n=3$ 个字符串，我们可以组合出 $3$ 种不同的 $t_{i,j}$： - 当 $i=1,j=2$ 时：$t_{1,2}=\mathtt{aaabaa}$。满足前缀等于后缀的长度 $x$ 有：$1,2,6$。 - 当 $i=1,j=3$ 时：$t_{1,3}=\mathtt{aaababaa}$。满足前缀等于后缀的长度 $x$ 有：$1,2,8$。 - 当 $i=2,j=3$ 时：$t_{2,3}=\mathtt{abaaababaa}$。满足前缀等于后缀的长度 $x$ 有：$1,4,10$。 最终答案为 $3+3+3=9$。