33OJ
登录 注册

#P17504. [ICPC 2026 Wuhan I] String Matching

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

[ICPC 2026 Wuhan I] String Matching

Problem Description

Given nn strings s1,s2,⋯ ,sns_1,s_2,\cdots,s_n consisting of lowercase letters. It is guaranteed that these strings are sorted in non-decreasing order of length, i.e. ∣s1∣≤∣s2∣≤⋯≤∣sn∣|s_1| \le |s_2| \le \cdots \le |s_n|.

For any two different strings sis_i and sjs_j with 1≤i<j≤n1 \le i<j \le n, define ti,j=si+sjt_{i,j}=s_i+s_j, which means the new string obtained by concatenating sis_i and sjs_j in order, with sis_i in front and sjs_j behind.

We define a function f(t)f(t), where tt is a string of length mm. The value of f(t)f(t) is the number of positive integers xx (0<x≤m0<x \le m) satisfying the following condition:

  • The first xx characters of string tt are exactly the same as the last xx characters of tt. That is, t[1:x]=t[m−x+1:m]t[1:x]=t[m-x+1:m].

Your task is to compute the sum of f(ti,j)f(t_{i,j}) over all valid pairs (i,j)(i,j), that is:

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

Input Format

The input contains multiple lines.

The first line contains an integer nn (1≤n≤1061 \le n \le 10^6), representing the total number of given strings.

The next nn lines each contain a lowercase string sis_i (1≤∣si∣≤1061 \le |s_i| \le 10^6).

It is guaranteed that the total length of all strings in the test data satisfies ∑∣si∣≤106\sum |s_i| \le 10^6.

Output Format

Output one line containing an integer, representing the total sum of all f(ti,j)f(t_{i,j}).

2
ak
hbcpc
1
3
aa
abaa
ababaa
9

Hint

In the second sample, there are n=3n=3 strings, and we can form 33 different ti,jt_{i,j}:

  • When i=1,j=2i=1,j=2: t1,2=aaabaat_{1,2}=\mathtt{aaabaa}. The lengths xx such that the prefix equals the suffix are: 1,2,61,2,6.
  • When i=1,j=3i=1,j=3: t1,3=aaababaat_{1,3}=\mathtt{aaababaa}. The lengths xx such that the prefix equals the suffix are: 1,2,81,2,8.
  • When i=2,j=3i=2,j=3: t2,3=abaaababaat_{2,3}=\mathtt{abaaababaa}. The lengths xx such that the prefix equals the suffix are: 1,4,101,4,10.

The final answer is 3+3+3=93+3+3=9.