【POJ 2001 Shortest Prefixes】 字典树(Trie树)

POJ2001
题意就是求一个能代表这个字符串的最短前缀，也就是只有这个字符串具有的前缀。
做法很显然，我们先构建好Trie树，然后对每个单词进行find，递归到直到节点出现次数为1，表示这个节点只有这一个单词走过，返回就ok。这里我用了string不断拼接字符，然后直接返回，减少了一些代码量。
POJ2001代码

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int maxn =2e6+5;
int tree[maxn][30];
int sum[maxn];
int tot;
void insert_(char *str)
{int  len=strlen(str);int root=0;for(int i=0;i<len;i++){int id=str[i]-'a';if(!tree[root][id]) tree[root][id]=++tot;sum[tree[root][id]]++;root=tree[root][id];}
}
string find_(char *str)
{int len=strlen(str);int root=0;string ans="";for(int i=0;i<len;i++){int id=str[i]-'a';root=tree[root][id];ans+=str[i];if(sum[root]==1) return ans;}
}
char ss[1005][25];
int main()
{int tot=0;while(scanf("%s",ss[tot++])!=EOF){insert_(ss[tot-1]);}for(int i=0;i<tot;i++){printf("%s %s\n",ss[i],find_(ss[i]).c_str());}return 0;
}