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

問題描述

給定若干字符串，對每個字符串找出其最短唯一前綴（即該前綴不作為其他任何字符串的前綴）。輸出格式：原字符串 最短前綴。

解法：Trie（字典樹）統計前綴計數

1. 構建 Trie，每個節點記錄 cnt：經過該節點的字符串數量
2. 插入所有字符串，沿路 cnt++
3. 對每字符串再次遍歷 Trie，首個 cnt==1 的節點即為最短唯一前綴終點

C++ 實現

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

struct Node {
    int cnt;
    Node* next[26];
    Node() : cnt(0) { memset(next, 0, sizeof(next)); }
};

Node* root = new Node();
char str[1010][25];

void insert(const char* s) {
    Node* p = root;
    for (int i=0; s[i]; ++i) {
        int c = s[i]-'a';
        if (!p->next[c]) p->next[c] = new Node();
        p = p->next[c];
        p->cnt++;
    }
}

void query(const char* s) {
    Node* p = root;
    for (int i=0; s[i]; ++i) {
        int c = s[i]-'a';
        p = p->next[c];
        putchar(s[i]);
        if (p->cnt == 1) break;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n = 0;
    while (cin >> str[n]) {
        insert(str[n]);
        ++n;
    }
    for (int i=0; i