給定一組單詞，對於每個單詞找出其最短的唯一前綴。所謂「唯一前綴」是指該前綴在所有單詞中只屬於該單詞，不會與其他單詞產生歧義。例如，單詞集合中有 "carbohydrate"、"cart"、"carburetor" 等，"carbohydrate" 的最短唯一前綴是 "carboh"，因為 "carbo" 同時也是 "carbon" 等詞的前綴，無法唯一標識。特別規定：若某單詞本身就是其他單詞的前綴（如 "car"），則該單詞自身即為其最短唯一前綴，因為精確匹配優先於前綴匹配。
輸入包含 2 到 1000 行，每行一個由 1 到 20 個小寫字母組成的單詞。輸出與輸入行數相同，每行輸出原單詞、一個空格，以及其最短唯一前綴。
本題是字典樹的經典應用。字典樹是一種樹形結構，每個節點代表一個字符，從根節點到某節點的路徑對應一個前綴。我們可以在每個節點記錄經過該節點的單詞數量（計數器）。
依次插入所有單詞。插入時，從根節點開始，對每個字符檢查對應的子節點是否存在：不存在則創建新節點並將計數器初始化為 1；存在則將該節點計數器加 1。最後到達的節點標記為單詞結尾（可選）。
對每個單詞，再次從根節點遍歷。沿路徑前進時，若遇到某節點的計數器為 1，說明該前綴僅屬於當前單詞，即為最短唯一前綴，輸出該前綴並停止。若遍歷完整個單詞仍未遇到計數器為 1 的節點，則該單詞本身即為最短唯一前綴（此時計數器必為 1，因為單詞不重複）。
設單詞總數為 N，平均長度為 L。構建字典樹時間 O(N·L)，查詢時間 O(N·L)，空間複雜度 O(N·L·字符集大小)，完全滿足題目限制（N ≤ 1000, L ≤ 20）。
struct TrieNode {
int cnt;
TrieNode* next[26];
TrieNode() : cnt(0) { memset(next, 0, sizeof(next)); }
};
void insert(TrieNode* root, const char* s) {
TrieNode* p = root;
for (int i = 0; s[i]; ++i) {
int idx = s[i] - 'a';
if (!p->next[idx]) p->next[idx] = new TrieNode();
p = p->next[idx];
p->cnt++;
}
}
void query(TrieNode* root, const char* s) {
TrieNode* p = root;
int i = 0;
for (; s[i]; ++i) {
p = p->next[s[i] - 'a'];
if (p->cnt == 1) break;
}
printf("%s %.*s\n", s, i + 1, s);
}
利用字典樹統計前綴出現次數，即可高效解決「最短唯一前綴」問題。此技巧廣泛應用於自動補全、IP 路由匹配、詞頻統計等場景。
