POJ 2001 Shortest Prefixes：Trie 樹求最短唯一前綴

題目大意

給定 2~1000 個單詞（長度 1-20），對每個單詞找最短前綴，使其在所有單詞中唯一標識該詞。完全匹配優先於前綴匹配（如 "car" 精確匹配 "car"，不視為 "carriage" 的前綴）。

Trie 樹 + 計數器

• 插入所有單詞，每個節點記錄 cnt（經過該節點的單詞數）
• 查詢時，從根遍歷單詞字符，第一個 cnt == 1 的節點即為最短唯一前綴結尾

C++ 代碼

struct TrieNode { int cnt, next[26]; } trie[20005];
int tot = 0;
char words[1005][25];

void insert(char* s) {
    int u = 0;
    for (int i = 0; s[i]; ++i) {
        int c = s[i] - 'a';
        if (!trie[u].next[c]) trie[u].next[c] = ++tot;
        u = trie[u].next[c];
        trie[u].cnt++;
    }
}

void find(char* s) {
    printf("%s ", s);
    int u = 0;
    for (int i = 0; s[i]; ++i) {
        printf("%c", s[i]);
        int c = s[i] - 'a';
        u = trie[u].next[c];
        if (trie[u].cnt == 1) break;
    }
    printf("\n");
}

int main() {
    int n = 0;
    while (~scanf("%s", words[++n])) insert(words[n]);
    for (int i = 1; i < n; ++i) find(words[i]);
    return 0;
}

關鍵點

• cnt 統計「有多少單詞經過此節點」
• cnt == 1 意味著從根到此的路徑只屬於當前單詞
• 完全匹配自然處理：若單詞本身無其他單詞共用前綴，會在最後一字符處 cnt==1

複雜度

• 時間：O(總長度) 插入 + O(總長度) 查詢
• 空間：O(總長度 × 26)