// 演算法：把每個容器字串「反轉後」插入字典樹，後綴比較變成前綴比較。
// Algorithm: insert each container word reversed into a Trie, turning the
// "longest common suffix" comparison into a "longest common prefix" walk.
// 每個節點記錄經過它的最佳容器索引（長度最短、其次索引最小）。
// Each node remembers the best container index passing through it
// (shortest length first, then smallest index). A query reversed then
// walks down as far as possible; the stop node's best index is the answer.

#include <string.h>   // strlen / 取字串長度
#include <stdlib.h>   // malloc, free / 動態記憶體
#include <limits.h>   // INT_MAX / int 的最大值

int* stringIndices(char** wordsContainer, int wordsContainerSize,
                   char** wordsQuery, int wordsQuerySize, int* returnSize) {
    // 先算出所有容器字串的總字元數，用來決定最多需要幾個節點（+1 給根節點）。
    // Count total characters across container words to size the Trie (+1 for root).
    long totalNodes = 1;                                  // 1 = 根節點 / the root
    for (int i = 0; i < wordsContainerSize; i++)
        totalNodes += (long)strlen(wordsContainer[i]);    // 每個字元最多新增一個節點 / each char may add one node

    // children[node][c] = 第 node 個節點、字母 c 方向的子節點編號，-1 表示沒有。
    // children[node][c] = child node id along letter c from `node`; -1 means none.
    // 寫法 int (*children)[26] 代表「指向一個含 26 個 int 的陣列」的指標，
    // i.e. a pointer to arrays-of-26-ints, so children[node] is one node's 26 slots.
    int (*children)[26] = malloc(sizeof(int[26]) * totalNodes);
    int *bestIdx = malloc(sizeof(int) * totalNodes);      // 每節點的最佳索引 / best index per node
    int *bestLen = malloc(sizeof(int) * totalNodes);      // 對應的字串長度 / its word length

    // 初始化根節點（編號 0）。 / Initialise the root (id 0).
    for (int j = 0; j < 26; j++) children[0][j] = -1;     // 26 個方向都還沒有子節點 / no children yet
    bestIdx[0] = -1;                                      // 尚未放入任何字串 / no word stored yet
    bestLen[0] = INT_MAX;                                 // 用最大值，任何真實長度都比它小 / so any real length wins
    int cnt = 1;                                          // 已使用節點數，下一個新節點用此編號 / next free node id

    // ---- 插入每個容器字串（反轉走訪）---- / insert each container word, reversed
    for (int i = 0; i < wordsContainerSize; i++) {
        int len = (int)strlen(wordsContainer[i]);         // 這個字串的長度 / length of this word
        int node = 0;                                     // 從根節點開始 / start at the root

        // 根節點代表「空後綴」，每個字串都會更新它。 / root = empty suffix, every word touches it.
        if (len < bestLen[0]) { bestLen[0] = len; bestIdx[0] = i; }  // 只在更短時覆蓋 → 同長保留較早者 / strict < keeps earliest on ties

        // 從字串「最後一個字元」往前走，等同走訪反轉字串。
        // Walk from the LAST character backwards = traversing the reversed string.
        for (int p = len - 1; p >= 0; p--) {
            int c = wordsContainer[i][p] - 'a';           // 字母轉成 0..25 的索引 / map 'a'..'z' to 0..25
            if (children[node][c] == -1) {                // 這個方向還沒有節點就新建一個 / create child if missing
                children[node][c] = cnt;                  // 記下新節點的編號 / link to the new node id
                for (int j = 0; j < 26; j++) children[cnt][j] = -1;  // 新節點清空子節點 / clear its children
                bestIdx[cnt] = -1;                        // 新節點尚無最佳值 / no best yet
                bestLen[cnt] = INT_MAX;
                cnt++;                                    // 消耗一個節點編號 / consume one node id
            }
            node = children[node][c];                     // 走到子節點 / descend into the child
            // 此節點代表目前已匹配的這段後綴，更新它的最佳索引。
            // This node represents the suffix matched so far; update its best index.
            if (len < bestLen[node]) { bestLen[node] = len; bestIdx[node] = i; }
        }
    }

    // ---- 回答每個查詢 ---- / answer each query
    int *ans = malloc(sizeof(int) * wordsQuerySize);      // 結果陣列 / the output array
    for (int i = 0; i < wordsQuerySize; i++) {
        int len = (int)strlen(wordsQuery[i]);
        int node = 0;                                     // 從根節點開始往下走 / start descending from root
        for (int p = len - 1; p >= 0; p--) {              // 同樣反轉走訪 / reversed walk again
            int c = wordsQuery[i][p] - 'a';
            if (children[node][c] == -1) break;           // 沒有共同後綴可延伸就停 / stop when no shared suffix
            node = children[node][c];                     // 否則繼續往下 / otherwise go deeper
        }
        ans[i] = bestIdx[node];                           // 停下節點的最佳索引就是答案 / best index here is the answer
    }

    *returnSize = wordsQuerySize;                         // 告訴呼叫者結果長度 / report output length
    free(children); free(bestIdx); free(bestLen);         // 釋放 Trie 記憶體，避免洩漏 / free Trie memory
    return ans;                                           // ans 由 LeetCode 接手釋放 / LeetCode frees ans
}