Index Pairs of Words in a Text

Given a string text and a list of distinct words, return every pair [i, j] such that the substring text[i..j] (inclusive) is one of the words. Return the pairs sorted by i, then by j.

Examples

Input:  text = "themightyoaktreeandme", words = ["might", "oak", "tree", "oaktree"]
Output: [[3, 7], [9, 11], [9, 15], [12, 15]]

Input:  text = "ababa", words = ["aba", "ab"]
Output: [[0, 1], [0, 2], [2, 3], [2, 4]]

Constraints

• 0 <= len(text) <= 5000, 0 <= len(words) <= 1000, words have length 1..50
• Lowercase letters only
• Target: O(len(text) * L) where L is the length of the longest word

Goals

• Scan a text from every start position along a trie
• Bound the inner loop by the longest stored word instead of the text length