A catalog lists n words indexed 0..n-1 in the given order (duplicate words may appear; the higher index wins). For each of q queries, each giving a prefix and a suffix, report the largest index i such that word i has the given prefix and the given suffix at the same time; if no word qualifies, report -1.
A standard trie method inserts, for every word, each of its suffixes joined to the whole word by a separator, so a single lookup keyed by suffix then separator then prefix resolves each query. All words, prefixes, and suffixes consist of lowercase English letters only.
Line 1: an integer n.
Line 2: n space-separated catalog words.
Line 3: an integer q.
Each of the next q lines: two space-separated strings, a prefix and a suffix.
Print q lines; line i is the answer to query i.
Example 1
Input
3 cat car cart 2 ca t car r
Expected
2 1
Explanation
For prefix ca and suffix t, cat (index 0) and cart (index 2) both match; the highest index is 2. For prefix car and suffix r, only car (index 1) matches (cart ends in t).
Example 2
Input
2 ab ab 1 a b
Expected
1
Explanation
Both copies of ab match prefix a and suffix b; the higher index 1 is reported.
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 →