All problems

Count Prefix and Suffix Pairs

Medium · trie

You are given a list words of lowercase words. The same word may appear more than once.

Count the pairs of positions (i, j) with i < j such that words[i] is both a prefix and a suffix of words[j]. In other words, words[j] begins with words[i] and also ends with words[i].

Every word is a prefix and a suffix of itself, so two equal words always form a pair. The prefix and the suffix are allowed to overlap: "aba" is both a prefix and a suffix of "ababa".

Return the number of such pairs.

Examples

Example 1

Input: words = ["a", "aba", "ababa", "aa"]

Output: 4

The pairs are ("a", "aba"), ("a", "ababa"), ("a", "aa") and ("aba", "ababa"). The word "aba" is not a suffix of "aa".

Example 2

Input: words = ["pa", "papa", "ma", "mama"]

Output: 2

Only "pa" in "papa" and "ma" in "mama" work. "pa" is not at the start of "mama".

Constraints