题目链接：http://poj.org/problem?id=2001
这道题目以前写过，复习一下字典树，再写一遍……
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cctype> 6 #include <set> 7 #include <map> 8 #include <vector> 9 #include <stack> 10 #include <queue> 11 #include <cmath> 12 #include <algorithm> 13 #define lson l, m, rt<<1 14 #define rson m+1, r, rt<<1|1 15 using namespace std; 16 typedef long long int LL; 17 const int MAXN = 0x3f3f3f3f; 18 const int MIN = -0x3f3f3f3f; 19 const double eps = 1e-9; 20 const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1}, 21 {1,1},{1,-1},{-1,-1}}; 22 char a[1000+10][30], base = 'a'; const int lo = 26; 23 typedef struct trie{ 24 int num; bool terminal; 25 struct trie *son[lo]; 26 }trie; 27 trie *newtrie(){ 28 trie *pnt = new trie; 29 pnt->num = 1; pnt->terminal = false; 30 for (int i = 0; i < lo; ++i) pnt->son[i] = NULL; 31 return pnt; 32 } 33 void insert(char str[], trie *pnt, int len){ 34 trie *tem = pnt; 35 for (int i= 0; i < len; ++i){ 36 if (tem->son[str[i]-base] != NULL){ 37 tem->son[str[i]-base]->num++; 38 } else{ 39 tem->son[str[i]-base] = newtrie(); 40 } tem = tem->son[str[i]-base]; 41 } 42 tem->terminal = true; 43 return; 44 } 45 void find(char str[], trie *pnt, int len){ 46 trie *tem= pnt; 47 for(int i = 0; i <len; ++i){ 48 if (tem->son[str[i]-base]->num == 1){ 49 printf("%c", str[i]); return; 50 } 51 printf("%c", str[i]); 52 tem= tem->son[str[i]-base]; 53 } 54 return; 55 } 56 int main(void){ 57 #ifndef ONLINE_JUDGE 58 freopen("2001.in", "r", stdin); 59 #endif 60 int cnt = 0, i = 0; trie *pnt = newtrie(); 61 while (~scanf("%s", a[i])){ 62 insert(a[i], pnt, strlen(a[i])); i++; 63 } 64 for (int j = 0; j < i; ++j){ 65 printf("%s ", a[j]); 66 find(a[j], pnt, strlen(a[j])); 67 printf("\n"); 68 } 69 70 return 0; 71 }
写的过程中还是出现了一些错误，比如，在第60行，开始写成了 trie * pnt = new trie; 只新建了一个节点没有初始化，悲剧的是，竟然可以运行，样例可以过，但是OJ上RE……还有，初始化结构体中的num的时候，要初始化为1,而不是0.查找的时候，要看当前节点的子节点的num是不是1,如果是1,先输出再返回，函数结束，而不是看当前节点的num的值是不是1,这样会多输出一个字符。