c++ - What's the correct approach to solve SPOJ www.spoj.com/problems/PRHYME/? -

c++ - What's the correct approach to solve SPOJ www.spoj.com/problems/PRHYME/? -

i have been trying solve problem spoj www.spoj.com/problems/prhyme/? several days, have had no success. here problem in brief:

given wordlist l, , word w. task find word in l forms perfect rhyme w. word u uniquely determined these properties:

it in l. it different w. their mutual suffix long possible. out of words satisfy previous points, u lexicographically smallest one.

length of word be<=30. , number of words both in dictionary , queries can 2,50,000.

i using trie store words in dictionary reversed. solve queries proceed in next fashion:-

if word nowadays in trie,delete trie. now traverse trie root till point character query string match trie values.let point lastly character match found p. now point p onward ,i traverse trie using dfs,and on encountering leaf node,push string formed possible results list. now homecoming lexicographic ally smallest result list.

when submit solution on spoj,my solution gets time limit exceeded error.

can please suggest detailed algorithm or hint solve problem ? can post code if required.

#include<iostream> #include<cstdio> #include<cstring> #include<climits> #include<vector> #include<string> #include<algorithm> #include<cctype> #include<cstdlib> #include<utility> #include<map> #include<queue> #include<set> #define ll long long signed int #define ull unsigned long long int const int alpha=26; using namespace std; struct node { int value; node * child[alpha]; }; node * newnode() { node * newt=new node; newt->value=0; for(int i=0;i<alpha;i++) { newt->child[i]=null; } homecoming newt; } struct trie { node * root; int count; trie() { count=0; root=newnode(); } }; trie * dict=new trie; string reverse(string s) { int l=s.length(); string rev=s; for(int i=0;i<l;i++) { int j=l-1-i; rev[j]=s[i]; } homecoming rev; } void insert(string s) { int l=s.length(); node * ptr=dict->root; dict->count++; for(int i=0;i<l;i++) { int index=s[i]-'a'; if(ptr->child[index]==null) { ptr->child[index]=newnode(); } ptr=ptr->child[index]; } ptr->value=dict->count; } void dfs1(node *ptr,string p) { if(ptr==null) return; if(ptr->value) cout<<"word" <<p<<endl; for(int i=0;i<26;i++) { if(ptr->child[i]!=null) dfs1(ptr->child[i],p+char('a'+i)); } } vector<string> results; pair<node *,string> search(string s) { int l=s.length(); node * ptr=dict->root; node *save=ptr; string match=""; int i=0; bool no_match=false; while(i<l , !no_match) { int in=s[i]-'a'; if(ptr->child[in]==null) { save=ptr; no_match=true; } else { ptr=ptr->child[in]; save=ptr; match+=in+'a'; } i++; } //cout<<s<<" matched till here"<<match <<" "<<endl; homecoming make_pair(save,match); } bool find(string s) { int l=s.length(); node * ptr=dict->root; string match=""; for(int i=0;i<l;i++) { int in=s[i]-'a'; //cout<<match<<"match"<<endl; if(ptr->child[in]==null) { homecoming false; } ptr=ptr->child[in]; match+=char(in+'a'); } //cout<<match<<"match"<<endl; homecoming true; } bool leafnode(node *pnode) { homecoming (pnode->value != 0); } bool isitfreenode(node *pnode) { int i; for(i = 0; < alpha; i++) { if( pnode->child[i] ) homecoming false; } homecoming true; } bool deletehelper(node *pnode, string key, int level, int len) { if( pnode ) { // base of operations case if( level == len ) { if( pnode->value ) { // unmark leaf node pnode->value = 0; // if empty, node deleted if( isitfreenode(pnode) ) { homecoming true; } homecoming false; } } else // recursive case { int index = (key[level])-'a'; if( deletehelper(pnode->child[index], key, level+1, len) ) { // lastly node marked, delete free(pnode->child[index]); pnode->child[index]=null; // recursively climb up, , delete eligible nodes homecoming ( !leafnode(pnode) && isitfreenode(pnode) ); } } } homecoming false; } void deletekey(string key) { int len = key.length(); if( len > 0 ) { deletehelper(dict->root, key, 0, len); } } string result="***"; void dfs(node *ptr,string p) { if(ptr==null) return; if(ptr->value ) { if((result)=="***") { result=reverse(p); } else { result=min(result,reverse(p)); } } for(int i=0;i<26;i++) { if(ptr->child[i]!=null) dfs(ptr->child[i],p+char('a'+i)); } } int main(int argc ,char ** argv) { #ifndef online_judge freopen("prhyme.in","r",stdin); #endif string s; while(getline(cin,s,'\n')) { if(s[0]<'a' , s[0]>'z') break; int l=s.length(); if(l==0) break; string rev;//=new char[l+1]; rev=reverse(s); insert(rev); //cout<<"...........traverse..........."<<endl; //dfs(dict->root); //cout<<"..............traverse end.............."<<endl; } while(getline(cin,s)) { results.clear(); //cout<<s<<endl; int l=s.length(); if(!l) break; string rev;//=new char[l+1]; rev=reverse(s); //cout<<rev<<endl; bool del=false; if(find(rev)) { del=true; //cout<<"here found"<<endl; deletekey(rev); } if(find(rev)) { del=true; //cout<<"here found"<<endl; deletekey(rev); } else { //cout<<"not here found"<<endl; } // cout<<"...........traverse..........."<<endl; //dfs1(dict->root,""); // cout<<"..............traverse end.............."<<endl; pair<node *,string> pp=search(rev); result="***"; dfs(pp.first,pp.second); //cout<<"search results"<<endl; //dfs1(pp.first,pp.second); //cout<<"end of search results"<< for(int i=0;i<results.size();i++) { results[i]=reverse(results[i]); // cout<<s<<" "<<results[i]<<endl; } string smin=result; if(del) { insert(rev); } cout<<smin<<endl; } homecoming 0; }

your algorithm (using trie stores reversed words) start. 1 issue each lookup, have enumerate words suffix in order find lexicographically smallest one. cases, can lot of work.

one way prepare this: in each node (corresponding each suffix), store 2 lexicographically smallest words have suffix. easy maintain while building trie updating ancestor nodes of each newly added leaf (see pseudo-code below).

then perform lookup of word w, start @ node corresponding word, , go in tree until reach node contains descendant word other w. homecoming lexicographically smallest word stored in node, or sec smallest in case smallest equal w.

to create trie, next pseudo-code can used:

for each word: add together word trie allow n node corresponding new word. each ancestor of n (including n): if a.smallest==null or word < a.smallest: a.second_smallest = a.smallest a.smallest = word else if a.second_smallest==null or word < a.second_smallest: a.second_smallest = word

to lookup word w:

let n node corresponding longest possible suffix of w. while ((n.smallest==w || n.smallest==null) && (n.second_smallest==w || n.second_smallest==null)): n = n.parent if n.smallest==w: homecoming n.second_smallest else: homecoming n.smallest

another similar possibility utilize hash table mapping suffixes 2 lexicographically smallest words instead of using trie. easier implement if can utilize std::unordered_map.

c++ string algorithm trie