A regional broadcast network issues every affiliate station a callsign made of uppercase letters. Engineers say a callsign A brackets a callsign B when A appears as both the prefix and the suffix of B — the two occurrences are allowed to overlap when A covers more than half of B's length, and A may equal B itself. Given the network's roster of n callsigns in the exact order they were issued, count how many index pairs (i, j) with i < j are such that callsign i brackets callsign j.
n.n+1: one callsign per line, a non-empty string of uppercase English letters.Print a single integer: the number of index pairs (i, j) with 0 <= i < j <= n-1 such that callsign_i is both a prefix and a suffix of callsign_j.
1 <= n <= 501 <= length of callsign_k <= 10 for every kA-Z)Example 1
Input
4 K KAK KAKAK KK
Expected
4
Explanation
Callsigns are K, KAK, KAKAK, KK. K brackets KAK, KAKAK, and KK (K is a prefix and suffix of each of them), and KAK brackets KAKAK (its first three and last three letters are both "KAK"). KAK does not bracket KK since KAK is longer than KK. Total: 4 pairs.
Example 2
Input
4 PA PAPA MA MAMA
Expected
2
Explanation
Callsigns are PA, PAPA, MA, MAMA. PA is both the prefix and suffix of PAPA, and MA is both the prefix and suffix of MAMA — two qualifying pairs. PA does not bracket MA or MAMA (they start with different letters), and no other index pair has the earlier callsign short enough to bracket the later one. Total: 2 pairs.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →