poj2001：http://poj.org/problem?id=2001
题意：给你一些单词，然后让你寻找每个单词的一个前缀，这个前缀能够唯一表示这个单词，并且是最短的。
题解：直接用trie树来搞。每个节点维护一个val值，每次插入经过该点值，把该点val加1，然后查询的时候，如果当前节点val是1，则说明只有一个串经过这里，此时就可以停止输出，返回即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define maxn 1100000
using namespace std;
struct Nod { //0为无效值
int lnk[], val;
void init() {
memset(lnk, , sizeof(lnk));
val = ;
}
};
const char BASE = 'a';
struct Trie {
Nod buf[maxn];
int len;
void init() {
buf[len=].init();
}
void insert(char * str) {
int now = ;
for(int i = ; str[i]; i ++) {
int & nxt = buf[now].lnk[str[i]-BASE];
if(!nxt)buf[nxt=++len].init();
now = nxt;
buf[now].val++;
}
}
void search(char * str) {
int now = ;
for(int i = ; str[i]; i ++) {
int & nxt = buf[now].lnk[str[i]-BASE];
printf("%c",str[i]);
if(buf[nxt].val==){
printf("\n");
return;
}
//if(!nxt) return 0;
now = nxt;
}
printf("\n");
}
} trie;
char str[][];
int main(){
int top=;
trie.init();
while(~scanf("%s",str[++top])){
trie.insert(str[top]);
}
for(int i=;i<=top;i++){
printf("%s ",str[i]);
trie.search(str[i]);
}
}