[UVA][Trie] 12506 - Shortest Names＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2012-11-11 17:20:22| 人1,351| 回0 | 上一篇 | 下一篇

[UVA][Trie] 12506 - Shortest Names

推 0 收藏 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 thenames. 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 villageare smart enough to always call the shortest possible prefix. It is guaranteed that no name is a prefix ofanother 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 exactlyonce, how many characters will he/she use?

Input

The first line contains T (T

10), the number of test cases. Each test case begins with a line of oneinteger n (1

1000), the number of people in the village. Each of the following n lines contains astring consisting of lowercase letters, representing the name of a person. The sum of lengths of all thenames in a test case does not exceed 1,000,000.

Output

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

Sample Input

13aaaaabbbabababab

Sample Output

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;
        }
        idx = Node[idx].link[str[i]-'a'];
        Node[idx].cnt++;
    }
    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]) {
&bsp;           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;
}