#P17504. [ICPC 2026 Wuhan I] String Matching
[ICPC 2026 Wuhan I] String Matching
Problem Description
Given strings consisting of lowercase letters. It is guaranteed that these strings are sorted in non-decreasing order of length, i.e. .
For any two different strings and with , define , which means the new string obtained by concatenating and in order, with in front and behind.
We define a function , where is a string of length . The value of is the number of positive integers () satisfying the following condition:
- The first characters of string are exactly the same as the last characters of . That is, .
Your task is to compute the sum of over all valid pairs , that is:
Input Format
The input contains multiple lines.
The first line contains an integer (), representing the total number of given strings.
The next lines each contain a lowercase string ().
It is guaranteed that the total length of all strings in the test data satisfies .
Output Format
Output one line containing an integer, representing the total sum of all .
2
ak
hbcpc
1
3
aa
abaa
ababaa
9
Hint
In the second sample, there are strings, and we can form different :
- When : . The lengths such that the prefix equals the suffix are: .
- When : . The lengths such that the prefix equals the suffix are: .
- When : . The lengths such that the prefix equals the suffix are: .
The final answer is .