P17504 [ICPC 2026 Wuhan I] String Matching

Given $n$ strings $s_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. $|s_1| \le |s_2| \le \cdots \le |s_n|$. For any two different strings $s_i$ and $s_j$ with $1 \le i

The input contains multiple lines. The first line contains an integer $n$ ($1 \le n \le 10^6$), representing the total number of given strings. The next $n$ lines each contain a lowercase string $s_i$ ($1 \le |s_i| \le 10^6$). It is guaranteed that the total length of all strings in the test data satisfies $\sum |s_i| \le 10^6$.

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

In the second sample, there are $n=3$ strings, and we can form $3$ different $t_{i,j}$: - When $i=1,j=2$: $t_{1,2}=\mathtt{aaabaa}$. The lengths $x$ such that the prefix equals the suffix are: $1,2,6$. - When $i=1,j=3$: $t_{1,3}=\mathtt{aaababaa}$. The lengths $x$ such that the prefix equals the suffix are: $1,2,8$. - When $i=2,j=3$: $t_{2,3}=\mathtt{abaaababaa}$. The lengths $x$ such that the prefix equals the suffix are: $1,4,10$. The final answer is $3+3+3=9$.