// 演算法與 C 版相同：反轉後插入字典樹，後綴比較變前綴走訪。
// Same algorithm as the C version: reverse words, insert into a Trie, so the
// longest-common-suffix query becomes a longest-common-prefix walk.
// 每個節點存「最佳容器索引」：長度最短優先，長度相同取較早索引。
// Each node stores the best container index: shortest length, ties broken by earliest index.

#include <vector>
#include <string>
#include <array>
#include <climits>
using namespace std;

class Solution {
public:
    vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
        // Trie 節點：26 個子節點（用 array 固定大小）+ 目前最佳索引與其長度。
        // Trie node: 26 children (fixed-size std::array) + the current best index and its length.
        struct Node {
            array<int, 26> children;   // children[c] = 子節點在 vector 中的位置，-1 表示沒有 / child id, -1 = none
            int bestIdx;               // 最佳容器索引 / best container index
            int bestLen;               // 最佳字串長度 / that word's length
            Node() : bestIdx(-1), bestLen(INT_MAX) { children.fill(-1); } // 建構時全部初始化 / init on construction
        };

        // 用 vector<Node> 當作節點池，索引就是節點編號；trie[0] 是根節點。
        // A vector<Node> is our node pool; the index is the node id; trie[0] is the root.
        vector<Node> trie(1);          // 先放一個根節點 / start with just the root

        // ---- 插入每個容器字串 ---- / insert each container word
        for (int i = 0; i < (int)wordsContainer.size(); i++) {
            const string& w = wordsContainer[i];   // const& 避免複製字串 / reference avoids copying the string
            int len = (int)w.size();
            int node = 0;                           // 從根開始 / start at root

            // 根節點對應空後綴，先更新它。 / root = empty suffix; update it first.
            if (len < trie[node].bestLen) { trie[node].bestLen = len; trie[node].bestIdx = i; } // strict < 保留較早者 / keeps earliest on ties

            // 從末尾往前 = 走訪反轉字串。 / iterate from the end = traverse the reversed word.
            for (int p = len - 1; p >= 0; p--) {
                int c = w[p] - 'a';                 // 字母轉 0..25 / map letter to 0..25
                if (trie[node].children[c] == -1) { // 需要新節點 / need to create a child
                    trie[node].children[c] = (int)trie.size();  // 新節點編號 = 目前大小 / new id = current size
                    trie.emplace_back();            // 在尾端就地建構一個 Node / build a Node in place at the back
                    // 注意：emplace_back 可能讓 vector 重新配置記憶體，
                    // 但我們全程用「索引」而非指標/參照存取，所以安全。
                    // Note: emplace_back may reallocate, but we only use indices (not pointers), so it's safe.
                }
                node = trie[node].children[c];      // 走到子節點 / descend
                if (len < trie[node].bestLen) { trie[node].bestLen = len; trie[node].bestIdx = i; } // 更新此後綴節點 / update this suffix node
            }
        }

        // ---- 回答查詢 ---- / answer the queries
        vector<int> ans;
        ans.reserve(wordsQuery.size());            // 預先配置容量，避免多次重新配置 / reserve to avoid reallocations
        for (const string& q : wordsQuery) {       // range-for：逐一取得每個查詢字串 / range-for over queries
            int node = 0;                          // 從根往下 / descend from root
            for (int p = (int)q.size() - 1; p >= 0; p--) {
                int c = q[p] - 'a';
                if (trie[node].children[c] == -1) break; // 無法再延伸共同後綴 / no further shared suffix
                node = trie[node].children[c];     // 繼續往下 / go deeper
            }
            ans.push_back(trie[node].bestIdx);     // 停下節點的最佳索引 / best index at the stop node
        }
        return ans;
    }
};