Count pairs of indices i < j for which words[i] matches both the beginning and the end of words[j]. A word is a prefix and a suffix of itself, so equal words at different indices qualify. The prefix and suffix may overlap. Return the number of qualifying index pairs; the order of the words in the array matters.
Example 1:
Input: words = ["b","bab","babab"]
Output: 3Explanation: The pairs (0,1), (0,2), and (1,2) qualify: b is at both ends of bab and babab, and bab is at both ends of babab. The answer is 3.
Example 2:
Input: words = ["xy","xy","xy"]
Output: 3Explanation: Every earlier copy of xy matches both ends of every later copy. The three index pairs (0,1), (0,2), and (1,2) are distinct, giving 3.
Example 3:
Input: words = ["ab","abc","zab"]
Output: 0Explanation: The word ab is only a prefix of abc and only a suffix of zab. No earlier word matches both ends of a later word, so the answer is 0.
Constraints:
1 <= words.length <= 1000001 <= words[i].length <= 100000- Every word contains only lowercase English letters.
- The total number of characters across all words is at most
500000.