967. Given the Start and the End

You are given n words, numbered from 0 in the order they appear, then q queries. Each query gives a prefix and a suffix. Print the LARGEST index of a word that both begins with the prefix and ends with the suffix, or -1 if no word does.

The same word may appear more than once in the list, and the largest index wins.

``` words apple(0) apply(1) ape(2) prefix ap, suffix le -> 0 prefix ap, suffix e -> 2 prefix z, suffix z -> -1

words ab(0) ab(1) ab(2) prefix a, suffix b -> 2 ```

## Two tries do not intersect

A trie of the words answers the prefix half and a trie of the reversed words, as in problem 961, answers the suffix half. Each gives a SET of word indices, and what is wanted is the largest index in their intersection. Storing the sets costs memory proportional to the number of matches, and intersecting them per query costs the size of the smaller set, which is exactly the work the trie was meant to avoid.

Scanning the word list instead costs q * n tests: at q = 20000 and n = 300 with strings of 10 letters that is 1.2 * 10^8 character comparisons.

## Make both halves into one prefix

Pick a separator character that cannot occur in a word, and insert, for every word, every key of the form

(a suffix of the word) + separator + (the whole word)

A word of length L produces L + 1 such keys, one per suffix including the empty suffix and the whole word. At each node along each key, record the largest word index seen so far.

A query becomes a single walk of the key

(the query suffix) + separator + (the query prefix)

and the answer is the index recorded at the node it lands on, or -1 if the walk falls off.

## Why that one walk is exactly the intersection

An inserted key contains the separator exactly once, at position equal to the length of the stored suffix. The query key also contains it exactly once. So the query key is a prefix of an inserted key if and only if the parts before the separators are equal AND the part after the query separator is a prefix of the part after the inserted one.

The first condition says the query suffix IS one of the word's suffixes, which is the same as saying the word ends with it. The second says the query prefix is a prefix of the word. Both halves of the question, enforced by one prefix walk.

The recorded maximum then reports the largest index among the words satisfying both, which is the answer.

## The separator matters

It must be outside the alphabet of the words, so the child array has 27 slots rather than 26. Reusing a letter breaks the argument above, because the key could then split in more than one place and a word could match a query it should not.

## The memory this costs, measured

With n = 300 words of at most 10 letters, the keys number at most 300 * 11 = 3300 and each is at most 21 characters, so the trie holds at most 3300 * 21 + 1 = 69301 nodes. At 27 links of 8 bytes each, that is 216 bytes a node, so at most 69301 * 216 = 14969016 bytes, about 15 MB.

That is the trade being made: roughly 15 MB and O(n * L^2) build time buy a query that costs the length of the key and nothing else. It scales badly in n and L, which is exactly why the limits on those are small here while q is large.

## Boundaries

An empty prefix or suffix is not allowed by the constraints here, but the whole word as both prefix and suffix is, and the construction handles it: the key word + separator + word is inserted because the full word is one of its own suffixes.

## Cost

Building is O(n * L^2) characters inserted, at most 300 * 11 * 21 = 69300 steps. Each query costs the length of its key, at most 21 steps. Nothing overflows.

Constraints - `1 ≤ n ≤ 300` - `1 ≤ q ≤ 20000` - Every word, prefix and suffix is 1 to 10 lowercase English letters. - Words may repeat, and indices run from 0 in input order.