Trie树模板题目（包含非正常模板）
题目链接：poj 2001
题意：给定若干字符串，对于每个字符串求出一个最短前缀，使得这个前缀不是任何其他字符串的前缀。
题解：水题直接上 Trie 树。
我思故我在：这个题要注意小心多输出一个空字符。
poj 2001
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
using namespace std;
char ap[1010][23];
vector<int> ve[230010];
char ad[230010][26];
char ans[300];
int fa[230010];
int size[230010];
int love=0;
int tot=0;
void dfs(int x,int y,int z)
{
if(z==strlen(ap[y]+1)+1) return ;
for(int i=0;i<ve[x].size();i++)
{
if(ad[x][i]==ap[y][z])
{
size[ve[x][i]]++,dfs(ve[x][i],y,z+1);
return;
}
}
ve[x].push_back(++love);
ad[x][ve[x].size()-1]=ap[y][z];
fa[love]=x,size[love]=1;
dfs(love,y,z+1);
}
int find(int x,int y)
{
if(size[x]!=1) return y;
else return find(fa[x],y+1);
}
void out(int x,int y,int z)
{
if(z==strlen(ap[y]+1)+1)
{
int p=find(x,0);
printf("%s ",ans+1);
for(int i=1;i<=z-max(p,1);i++)
printf("%c",ans[i]);
if(y!=tot)
puts("");
}
for(int i=0;i<ve[x].size();i++)
{
// printf("%c",ad[x][i]);
if(ad[x][i]==ap[y][z])
{
ans[z]=ad[x][i];
out(ve[x][i],y,z+1);
ans[z]=0;
}
}
}
int main()
{
while(scanf("%s",ap[++tot]+1)!=EOF)
{
dfs(0,tot,1);
}
for(int i=1;i<=tot;i++)
out(0,i,1);
return 0;
}