2012-11-11 17:20:22Morris
[UVA][Trie] 12506 - Shortest Names
Shortest Names
| 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 (1n1000), 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
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;
}
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]) {
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;
}