题意:给一堆字符串,输出对应字符串能区别于别的字符串的缩写。
思路:记录下每个点经过的次数,那么对每个字符串,直到找到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; }