投資錢景>買台積電就對了新手>新婚族選績優龍頭股 攝影界美人正妹指定相機款24天後重啟院會 兩岸...
2012-11-11 17:20:22 人氣(388) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][Trie] 12506 - Shortest Names

0
收藏
0
推薦


  Shortest Names 

In a strange village, people have very long names. For example: aaaaa, bbb and abababab.

You see, it's very inconvenient to call a person, so people invented a good way: just call a prefix of the names. For example, if you want to call `aaaaa', you can call `aaa', because no other names start with `aaa'. However, you can't call `a', because two people's names start with `a'. The people in the village are smart enough to always call the shortest possible prefix. It is guaranteed that no name is a prefix of another name (as a result, no two names can be equal).

If someone in the village wants to call every person (including himself/herself) in the village exactly once, how many characters will he/she use?

Input 

The first line contains T (T$ le$10), the number of test cases. Each test case begins with a line of one integer n ( 1$ le$n$ le$1000), the number of people in the village. Each of the following n lines contains a string consisting of lowercase letters, representing the name of a person. The sum of lengths of all the names in a test case does not exceed 1,000,000.

Output 

For each test case, print the total number of characters needed.

Sample Input 

1
3
aaaaa
bbb
abababab

Sample Output 

5



Problemsetter: Rujia Liu, Special Thanks: Yiming Li, Feng Chen, Jane Alam Jan

#include <stdio.h>
#include <string.h>
struct Trie {
    bool n;
    int link[26], cnt;
} Node[1048576];
int TrieSize;
int insertTrie(const char *str) {
    static int i, idx;
    idx = 0;
    for(i = 0; str[i]; i++) {
        if(!Node[idx].link[str[i]-'a']) {
            TrieSize++;
            memset(&Node[TrieSize], 0, sizeof(Node[0]));
            Node[idx].link[str[i]-'a'] = TrieSize;
        }
        Node[idx].cnt++;
        idx = Node[idx].link[str[i]-'a'];

    }
    Node[idx].n = true;
    return 0;
}
long long ans;
void dfs(int nd, int dep) {
    int i;
    for(i = 0; i < 26; i++) {
        if(Node[nd].link[i]) {
            dfs(Node[nd].link[i], dep+1);
            if(Node[nd].cnt != 1 && Node[Node[nd].link[i]].cnt == 1)
                ans += dep;
        }
    }
}
char str[10000];
int main() {
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        TrieSize = 0;
        memset(&Node[0], 0, sizeof(Node[0]));
        while(n--) {
            scanf("%s", str);
            insertTrie(str);
        }
        ans = 0;
        dfs(0, 1);
        printf("%lld\n", ans);
    }
    return 0;
}

12506Shortest NamesTrie
台長:Morris
人氣(388) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][ST] 12532 - Interval Product
此分類上一篇:[UVA][dp] 526 - String Distance and Transform Process

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文