POJ 3630 Phone List(Trie树，静态数组实现)
/*这道题动态分配内存会超时先建图，建图完成后，再判断，这样不容易出错*//*解法一：Trie树，静态数组实现*/#include <cstdio>#include <cstring>const int nMax = 200000;struct Trie{Trie *next[10];int count;}trie[nMax];int pos;void buildTrie(char *s, int len){Trie *p = &trie[0];int i;for(i = 0; i < len; ++ i){int index = s[i] - '0';if(p->next[index] == NULL) p->next[index] = &trie[pos ++];//模拟动态分配内存p = p->next[index];}p->count ++;}bool judge(Trie *root)//学会使用函数的返回值，减少全局变量的使用有时候可以简化程序复杂度{int i;if(root->count > 1) return 1;for(i = 0; i < 10; ++ i){if(root->next[i]){if(root->count > 0) return 1;if(judge(root->next[i])) return 1;//原来这里没有做处理}}return 0;}int main(){//freopen("e://data.in", "r", stdin);int T;scanf("%d", &T);while(T --){int N;scanf("%d", &N);int i;char s[15];pos = 1;memset(trie, 0, sizeof(trie));//memset可以对数组进行初始化for(i = 0; i < N; ++ i){scanf("%s", s);int len = strlen(s);buildTrie(s, len);}printf("%s\n", judge(&trie[0]) ? "NO" : "YES");}return 0;}/*解法二：哈希表实现*/#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int HASH = 12007;int T, N;char s[10007][15];int flag;char hash[HASH][15];int head[HASH];int fhash(char *s, int len){int p = 0;int i;for(i = 0; i < len; ++ i)p = (p * 10 + s[i] - '0') % HASH;return p;}int insert(char *s, int len){int p = fhash(s, len);while(head[p] != 0 && strcmp(s, hash[p]) != 0){p = (p + 1) % HASH;}if(head[p] == 0){strcpy(hash[p], s);head[p] = 1;return 1;}return 0;}bool isFind(char *s, int len){char ss[15];int i;for(i = 0; i < len; ++ i)ss[i] = s[i];ss[len] = '\0';int p = fhash(ss, len);while(head[p] != 0 && strcmp(ss, hash[p]) != 0){p = (p + 1) % HASH;}if(head[p] == 0){return 0;}return 1;}int main(){//freopen("e://data.in", "r", stdin);int T;scanf("%d", &T);while(T --){memset(head, 0, sizeof(head));scanf("%d", &N);int i, j;int len;flag = 0;for(i = 0; i < N; ++ i){scanf("%s", s[i]);if(flag == 0){len = strlen(s[i]);if(!insert(s[i], len)){flag = 1;}}}for(i = 0; i < N && !flag; ++ i){len = strlen(s[i]);for(j = 1; j < len && !flag; ++ j)if(isFind(s[i], j))flag = 1;}if(flag)printf("NO\n");elseprintf("YES\n");}return 0;}