#include<algorithm> #include<iostream> #include<Cstring> using namespace std; const int MAX=1e5; char s[5005][26]; int tree[5005][26]; int val[50005]; int cnt=1; void Build(char s[]){ int len=strlen(s); int root = 0; for(int i=0; i<len; i++){ int next = s[i]-'a'; if(!tree[root][next]) tree[root][next]=cnt++; root=tree[root][next]; val[root]++; } } string search(char s[]){ string ans; int root=0; int len=strlen(s); for(int i=0;i<len;i++){ if(val[root]==1) return ans; int next=s[i]-'a'; ans+=s[i]; root=tree[root][next]; } return ans; } int main(){ memset(val,0,sizeof(val)); int n=0; while(scanf("%s",s[n])!=EOF){ Build(s[n]); n++; } for(int i=0;i<n;i++){ cout<<s[i]<<" "<<search(s[i])<<endl; } return 0; } |
Double click to view unformatted code.