PKU 3450 Corporate Identity
http://poj.org/problem?id=3450
n個の文字列が与えられる。すべての文字列に含まれている連続する部分列のうち最長かつ辞書順最小のものを答えろというような問題。
trieを使って頑張りました。
PKUにしては時間があまり厳しくないように感じました。
typedef struct _node{ char key; int size; _node* next[26]; }node; node ent[100000]; int sz; node root; int msz; void insert(char* str,int si){ int tsz=0; node*p=&root; for(;*str;++str){ if(si!=1 && p->next[*str-'a']==NULL)break; if(p->next[*str-'a']==NULL)p->next[*str-'a']=ent+sz++; p=p->next[*str-'a']; if(p->size<si-1)break; p->size=si; p->key=*str; msz=max(msz,++tsz); } } int n; char outbuff[200]; bool pr(node*p,int t){ if(t==msz){ cout<<outbuff<<endl; return true; } rep(i,26) if(p->next[i] && p->next[i]->size==n){ outbuff[t]=i+'a'; if(pr(p->next[i],t+1)){ outbuff[t]=0; return true; } outbuff[t]=0; } return false; } char str[200]; main(){ while(cin>>n,n){ memset(ent,0,sizeof(ent)); memset(root.next,0,sizeof(root.next)); sz=0; rep(i,n){ cin>>str; int ssz=strlen(str); msz=0; rep(j,ssz)insert(str+j,i+1); } if(msz)pr(&root,0); else cout<<"IDENTITY LOST"<<endl; } }