Framing Word Pairs

Hard

You get a list of words words. Say that a word a **frames** a word b if b both starts and ends with a. For example, "aba" frames "ababa", while "abc" does not frame "abcd". Every word frames itself. Count the index pairs (i, j) with i < j such that words[i] frames words[j].

Example 1

words=['ab', 'abab', 'b', 'ab'] → 2

"ab" both starts and ends "abab" (pair (0, 1)), and the second "ab" matches the first one entirely (pair (0, 3)). "b" does not start any later word.

Example 2

words=['xyx', 'x', 'xyxyx'] → 2

Both "xyx" and "x" frame "xyxyx" on both sides. The pair (0, 1) does not count because the longer word comes first.

Constraints

1 ≤ len(words) ≤ 10⁵
1 ≤ len(words[i]) ≤ 10⁵
The total length of all words is at most 5·10⁵
Words consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Trie Array String String Matching Hash Function Rolling Hash

Similar problems

Bookend Word Pairs Easy Target From Word Beginnings Medium Phrase From Word Beginnings, Long Edition Hard Palindrome by Adding Letters in Front Hard Doubled Fragments Hard

Input

words=['ab', 'abab', 'b', 'ab']

Expected

Run checks the first 3 tests in your browser. Submit checks all 71 tests on the server, hidden ones included.