UVA 11486 Hyper Prefix Sets：字典樹（Trie）求最大權值前綴

問題描述

給定 n 個字符串，需找到一個字符串 u 作為前綴，使得 u 的長度 |u| 乘以以 u 為前綴的字符串數量 cnt(u) 最大。輸出最大權值 max |u| * cnt(u)。字符集為可見 ASCII（32~126），共 95 個字符。多組測試數據。

字典樹解法

將所有字符串插入字典樹。每個節點維護：

• cnt：以該節點結尾的字符串數（即有多少字符串以此前綴開頭）。
• depth：該節點對應的前綴長度（根深度 0）。

答案即為所有節點中 depth * cnt 的最大值。

完整 C++ 代碼

#include <bits/stdc++.h>
using namespace std;

struct Trie {
    static const int MAXN = 500010;  // 總字符數上限
    static const int SIGMA = 95;     // 可見字符 32~126
    int ch[MAXN][SIGMA];
    int cnt[MAXN];
    int depth[MAXN];
    int sz;

    Trie() { clear(); }

    void clear() {
        sz = 1; // 0 為根
        memset(ch[0], 0, sizeof(ch[0]));
        cnt[0] = depth[0] = 0;
    }

    int idx(char c) { return c - 32; }

    void insert(const char* s) {
        int u = 0;
        for (int i = 0; s[i]; ++i) {
            int c = idx(s[i]);
            if (!ch[u][c]) {
                ch[u][c] = sz;
                memset(ch[sz], 0, sizeof(ch[sz]));
                cnt[sz] = 0;
                depth[sz] = depth[u] + 1;
                sz++;
            }
            u = ch[u][c];
            cnt[u]++;
        }
    }

    long long queryMax() {
        long long ans = 0;
        queue<int> q;
        q.push(0);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            ans = max(ans, 1LL * depth[u] * cnt[u]);
            for (int c = 0; c < SIGMA; ++c) {
                if (ch[u][c]) q.push(ch[u][c]);
            }
        }
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        Trie trie;
        int n; cin >> n;
        string s;
        while (n--) {
            cin >> s;
            trie.insert(s.c_str());
        }
        cout << trie.queryMax() << '\n';
    }
    return 0;
}

關鍵點總結

• 字符映射：c - 32 將可見字符壓縮到 [0, 94]。
• 插入時沿路遞增 cnt，表示有多少字符串通過此節點（即以此前綴開頭）。
• BFS/DFS 遍歷所有節點計算 depth * cnt 最大值。
• 內存估算：最大總長度 500,000，節點數 ≤ 總長度 + 1，ch[500010][95] 約 1.9 億 int ≈ 760 MB，較大。實際可用 vector<array<int,95>> 或動態分配（如 map/unordered_map）優化，但題目數據通常允許靜態數組通過。

複雜度

• 構建：O(總字符長度 * 1)。
• 查詢：O(節點數 * SIGMA)。
• 總體線性於輸入規模。

變體延伸

若需輸出具體達到最大權值的前綴字符串，可在節點存儲父指針與字符，找到最大值節點後回溯構造字符串。