UVA 11732 strcmp() Anyone?：Trie 樹統計字符串比較次數

UVA 11732 strcmp() Anyone?：Trie 樹統計字符串比較次數

給定 n 個字符串，模擬兩兩 strcmp 比較，統計總字符比較次數。strcmp 逐字符比較，相等繼續，不同或遇 '\0' 停止。注意：相等字符串還需比較結束符，計 2 次（字符相等 1 次 + '\0' 比較 1 次）。

Trie 樹累加法

插入字符串時，沿路徑累加比較次數：

• 當前節點有多個子節點，插入新字符需與所有現有子節點比較：相同字符子節點計 2 次（字符+'\0'），不同字符計 1 次（字符不同即停止）。
• 實現：每個節點記錄 val = 以此節點為前綴的字符串數（含結束）。

核心代碼

struct Node { char c; int val; } node[4000005];
int first[4000005], nxt[4000005], sz;
long long ans;

void insert(char* str) {
    int u = 0, len = strlen(str);
    for (int i=0; i<=len; i++) { // 包含結束符 '\0'
        bool found = false; int v;
        for (v = first[u]; v; v = nxt[v]) {
            if (node[v].c == str[i]) {
                found = true;
                ans += node[v].val * 2; // 相同字符：比較字符 + 比較'\0'
                break;
            } else {
                ans += node[v].val; // 不同字符：只比較字符
            }
        }
        if (!found) {
            v = sz++;
            node[v].c = str[i];
            node[v].val = 0;
            first[v] = 0;
            nxt[v] = first[u];
            first[u] = v;
        }
        u = v;
        node[u].val++;
    }
}

int main() {
    int n, cas=0;
    while (scanf("%d", &n) == 1 && n) {
        sz = 1; ans = 0; first[0]=0;
        char str[1005];
        while (n--) {
            scanf("%s", str);
            insert(str);
        }
        printf("Case %d: %lld\n", ++cas, ans);
    }
}

關鍵細節

1. 插入包含結束符：循環 i<=len，str[len]=='\0'。
2. 節點 val 計數：每插入一個字符串（含結束），沿路徑所有節點 val++。
3. 比較次數累加邏輯：遍歷當前節點所有子節點，相同字符累加 val*2，不同累加 val。
4. 靜態數組實現 Trie：first[] 頭指針，nxt[] 鏈表，避免動態分配開銷。

複雜度

• 總字符數 ≤ 1000×1000 = 1e6，Trie 節點數同階，O(總長度) 極快。

對比：排序 + 相鄰比較

字符串排序後，僅需比較相鄰對的 LCP（最長公共前綴），但需處理所有配對的比較次數，Trie 直接構建過程中累加更直觀高效。

此題是 Trie 統計應用的經典例題，展示了「構建過程即計算」的思想。