You are given two arrays of strings, wordsContainer and wordsQuery.

For each string wordsQuery[i], find the string in wordsContainer that shares the longest common suffix with it.

• If multiple strings in wordsContainer share the same longest suffix, choose the one with the smallest length.

• If two or more such strings have the same smallest length, choose the string that appears earliest in wordsContainer.

Return an array of integers ans, where ans[i] is the index of the chosen string in wordsContainer for the query wordsQuery[i].

Constraints:

• $1 \leq$ wordsContainer.length, wordsQuery.length $\leq 10^4$

• $1 \leq$ wordsContainer[i].length $\leq 5 * 10^3$

• $1 \leq$ wordsQuery[i].length $\leq 5 * 10^3$

• wordsContainer[i] consists only of lowercase English letters.

• wordsQuery[i] consists only of lowercase English letters.

• Sum of wordsContainer[i].length is, at most $5 * 10^5$.

• Sum of wordsQuery[i].length is, at most $5 * 10^5$.

To solve the problem, build a reversed trie from wordsContainer, where each node represents a character from the end of a word toward its start. We insert each word back-to-front so that suffix matching becomes prefix matching. Store the best candidate at every node as a pair (index, length), where “best” means smallest length, and if lengths tie, the earliest index in wordsContainer. For each word in wordsContainer, start from the root, update the stored best candidate if the current word is smaller (or first in order for ties), and then insert its characters in reverse, updating the best candidate at every step. Once the trie is built, the algorithm processes each word in wordsQuery by traversing the trie in reverse character order, stopping if a character path does not exist. The best candidate index stored at the last visited node is then appended to the result list.

The steps of the algorithm are as follows:

1. Create an empty dictionary trie to serve as the root node. Each node maps characters to child nodes and uses the special key None to store the best candidate as (index, length).

2. Build the reversed trie from wordsContainer:
   For each (index, word) in wordsContainer:

   1. Set currentNode = trie.

   2. At the root, set currentNode[None] to (index, len(word)) if it’s unset or if len(word) < currentNode[None][1] (i.e., the current word has the smallest length so far). If lengths are equal, retain the existing pair so the earlier index remains.

   3. Iterate through the characters of the word in reverse:

      1. Create the child node for char if absent, then move currentNode to that child.

      2. At each node, update the stored best candidate using the same rule (prefer smallest length; on equal length, retain the already stored candidate (corresponding to the earliest index seen on this path).

3. Query the trie using wordsQuery:
   Initialize result = []. For each queryWord in wordsQuery:

   1. Set currentNode = trie.

   2. Traverse the trie using the characters of queryWord in reverse, stopping if a required char is not present.

   3. After the traversal, append currentNode[None][0] (the stored best candidate’s index) to result.

4. Return result, the list of indices in wordsContainer corresponding to the smallest words among those sharing the longest common suffix with each queryWord.

Let’s look at the following illustration to get a better understanding of the solution: