POJ 2001 Shortest Prefixes 字典树

题意很好理解就不说了，然后这道题其实不用字典树更简单，但是为了练习trie树就写了一下，1A了哈哈，再对比了一下讨论区的大神代码，发现我还是写复杂了。。。

思路：

想到利用字典树，继承字典树原有机制，从底端叶子向上找，每条路径最先找

到的分叉点再往下（从叶子找上来的这条路）一个字符即为所求（特殊情况，

如果节点处单词已结束，那么就输出整个单词好了），也就是从上往下找到的

第一个不是路径重合（has_same_path = true）的情况或者是is_word =

true的情况，用遍历二叉树的方法遍历整个树得到所有前缀。
判断has_same_path的情况很简单，如果当前tmp->next[num]不为空，则

一定has_same_path
，至于pos则是为了让答案按顺序输出用的

代码：

/*
poj      2001
11152K	16MS
*/
#include
  
   
#include
   
     #include
    
      #include
     
       #define MAXN 1005 using namespace std; struct node { node *next[26]; bool has_same_path; bool is_word; int pos; node() { memset(next , 0 , sizeof(next)); has_same_path = is_word = false; pos = -1; } }trie[100005]; int trie_num; struct out { char s[21]; int pos; out() { memset(s , 0 , sizeof(s)); pos = -1; } }ans[MAXN]; int n = 1,id; char str[MAXN][21],tmp_str[21]; bool cmp(out a , out b) { return a.pos < b.pos; } void insert(char *s , int pos)//插入单词 { int len = strlen(s); node *now = &trie[0]; for(int i = 0;i < len;i ++) { int num = s[i] - 'a'; if(!now->next[num]) now->next[num] = &trie[++trie_num]; else now->next[num]->has_same_path = true; now = now->next[num]; if(now->pos == -1) now->pos = pos; } now->is_word = true; now->pos = pos; } void cons(node *now , int k)//构造答案 { if(!now->has_same_path || now->is_word) { tmp_str[k] = 0; memcpy(ans[++id].s , tmp_str , k); ans[id].pos = now->pos; now->is_word = false;//防止回溯时再次计入 if(!now->has_same_path) return ; } for(int i = 0;i < 26;i ++) { if(now->next[i]) { tmp_str[k] = i + 'a'; cons(now->next[i] , k + 1); } } } int main() { while(scanf("%s" , str[n]) != EOF) { insert(str[n] , n); n ++; } n --; trie[0].has_same_path = true; cons(&trie[0] , 0); sort(ans + 1 , ans + n + 1 , cmp); for(int i = 1;i <= n;i ++) printf("%s %s\n",str[i] , ans[i].s); return 0; }