题意：给出一些单词，找出每个单词的最短前缀，这个前缀不能有歧义。即不能和其他单词的前缀相同。
题记：字典树的模板题，先把所有单词都放进字典树中，num[]记录以某一字符串为前缀的单词的数量，在Find()时如果以当前字符串为前缀的单词数量只有1个，直接break。如果找不到，这个单词的前缀就是它本身。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
typedef long long ll;
const int N=5e4+10;
int num[N];
string s,sl[5001];
int trie[N][27],pos=1;
void Insert(string s){int len=s.size();int p=0;for(int i=0;i<len;i++){int c=s[i]-'a';if(!trie[p][c])trie[p][c]=pos++;p=trie[p][c];num[p]++;}
}
void Find(string s){for(int i=0;i<s.size();i++) printf("%c",s[i]);printf(" ");int p=0;for(int i=0;i<s.size();i++){printf("%c",s[i]);p=trie[p][s[i]-'a'];if(num[p]==1)break;}printf("\n");
}
int main(){//IOS;int t=0;while(cin>>s){Insert(s);sl[++t]=s;}for(int i=1;i<=t;i++)Find(sl[i]);return 0;
}