题意：给你一组串，求每个串在组中唯一标志的最短前缀
分析：保存树上经过各节点的单词个数，扫描每个串当经过节点单词个数是一（能唯一标志）结束
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
#define N 20010
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = ;
struct Trie{
int ch[N][];
int val[N],num;
void init(){
num=;
memset(ch[],,sizeof(ch[]));
}
int idx(char c){return c-'a';}
//建树
void build(char *s){
int u=,n=strlen(s);
for(int i=;i<n;++i){
int v=idx(s[i]);
if(!ch[u][v]){
memset(ch[num],,sizeof(ch[num]));
ch[u][v]=num++;
}
u=ch[u][v];
val[u]++;
}
}
//查询
void query(char *s){
int u=,n=strlen(s);
for(int i=;i<n;++i){
int v=idx(s[i]);
u=ch[u][v];
printf("%c",s[i]);
if(val[u]==){
break;
}
}
printf("\n");
}
}trie;
int main()
{
trie.init();
char a[][];
int id=;
while(~scanf("%s",a[id])){
trie.build(a[id]);
id++;
}
for(int i=;i<id;++i){
printf("%s ",a[i]);
trie.query(a[i]);
}
return ;
}