题意：给一堆字符串，输出对应字符串能区别于别的字符串的缩写。
思路：记录下每个点经过的次数，那么对每个字符串，，直到找到p->cnt=1为止。详见代码：
/********************************************************* file name: poj2001.cpp author : kereo create time: 2015年02月10日 星期二 08时51分10秒*********************************************************/#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<set>#include<map>#include<vector>#include<stack>#include<cmath>#include<string>#include<algorithm>using namespace std;typedef long long ll;const int sigma_size=26;const int N=10000+50;const int MAXN=2000000+50;const int inf=0x3fffffff;const double eps=1e-8;const int mod=1000000000+7;#define L(x) (x<<1)#define R(x) (x<<1|1)#define PII pair<int, int>#define mk(x,y) make_pair((x),(y))int sz,cnt;char str[N][25];struct node{int cnt,id;node *ch[sigma_size];}nod[MAXN],nil,*root,*null;struct Trie{void init(){sz=0;nil.cnt=nil.id=0; null=&nil;newnode(root);}void newnode(node *&x){x=&nod[sz]; x->cnt=0; x->id=sz++;for(int i=0;i<sigma_size;i++)x->ch[i]=null;}void insert(char *str){int len=strlen(str);node *p=root;for(int i=0;i<len;i++){int k=str[i]-'a';if(p->ch[k] == null)newnode(p->ch[k]);p=p->ch[k]; p->cnt++;}}void print(char *str){printf("%s ",str);int len=strlen(str);node *p=root;for(int i=0;i<len;i++){int k=str[i]-'a';printf("%c",str[i]);p=p->ch[k];if(p->cnt == 1)break;}printf("\n");}}trie;int main(){//freopen("in.txt","r",stdin);cnt=0;trie.init();while(~scanf("%s",str[cnt])){trie.insert(str[cnt++]);}for(int i=0;i<cnt;i++)trie.print(str[i]);return 0;}
人生不如意十之八-九，与其诅咒黑暗，倒不如在生命中点燃一盏灯
