#include #include #include #include #include using namespace std; class Trie { public: int value; vector children; Trie(){ children.resize('z'-'a'+1, 0); value=0; } }; void add(Trie *(&p), const char *s){ if(*s == '\0'){ p->value=1; } else{ if(p->children[*s-'a'] == 0){ p->children[*s - 'a'] = new Trie; } add(p->children[*s - 'a'], s+1); } } void checkfront(Trie *root, const char *s, int ind, vector &good) { if(*s == '\0') return; if(root->children[*s -'a']!=0){ if(root->children[*s-'a']->value==1) good[ind]=1; if(*(s+1)) checkfront(root->children[*s-'a'],s+1,ind+1,good); } } bool check(Trie *(&root), const char *s){ //cout<<"check for "< good(sl,0); checkfront(root, s, 0, good); for(int i=0;s[i]!='\0' && s[i+1]!='\0';++i){ if(good[i]){ //cout<<" checking "<>n; vector words(n); for(auto &s : words) cin>>s; sort(words.begin(),words.end(),mycmp); Trie *root= new Trie; string longest=""; for(auto& w : words){ if(check(root, w.c_str())){ if(w.size()>longest.size()) longest=w; } add(root,w.c_str()); } if(longest=="") cout<<"-1\n"; else cout<