Какой правильный подход к решению SPOJ www.spoj.com/problems/PRHYME/?

Я пытался решить эту проблему SPOJ www.spoj.com/problems/PRHYME/? в течение нескольких дней, но не имели успеха.
Вот проблема вкратце:

Дан список слов L и слово w. Ваша задача — найти слово в L, которое образует идеальную рифму с w. Это слово u однозначно определяется этими свойствами:

• Это в Л.
• Это отличается от ш.
• Их общий суффикс максимально длинный.
• Из всех слов, которые удовлетворяют предыдущим пунктам, u является лексикографически наименьшим.

Длина слова будет<= 30.
А количество слов как в словаре, так и в запросах может быть 2,50000.

Я использую три для хранения всех слов в словаре в обратном порядке.
Затем для решения запросов я поступаю следующим образом:

1. Если в дереве есть слово, удалите его из дерева.
2. Теперь пройдитесь по дереву от корня до точки, в которой символ из строки запроса соответствует значениям дерева. Пусть эта точка, где было найдено последнее совпадение символов, равна P.
3. Теперь, начиная с этой точки P, я пересекаю дерево, используя DFS, и, встречая конечный узел, вставляю сформированную строку в список возможных результатов.
4. Теперь я возвращаю лексикографическому союзнику самый маленький результат из этого списка.

Когда я отправляю свое решение на SPOJ, мое решение получает ошибку превышения лимита времени.

Может кто-нибудь предложить подробный алгоритм или подсказку для решения этой проблемы?
Я могу опубликовать свой код, если требуется.

#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 intconst 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;
}
return 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];

}

return 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 and !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;
return 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)
{
return false;
}
ptr=ptr->child[in];
match+=char(in+'a');
}
//cout<<match<<"match"<<endl;

return true;}
bool leafNode(node *pNode)
{
return (pNode->value != 0);
}

bool isItFreeNode(node *pNode)
{
int i;
for(i = 0; i < alpha; i++)
{
if( pNode->child[i] )
return false;
}

return true;
}
bool deleteHelper(node *pNode, string key, int level, int len)
{
if( pNode )
{
// Base case
if( level == len )
{
if( pNode->value )
{
// Unmark leaf node
pNode->value = 0;

// If empty, node to be deleted
if( isItFreeNode(pNode) )
{
return true;
}

return false;
}
}
else // Recursive case
{
int index = (key[level])-'a';

if( deleteHelper(pNode->child[index], key, level+1, len) )
{
// last node marked, delete it
free(pNode->child[index]);
pNode->child[index]=NULL;

// recursively climb up, and delete eligible nodes
return ( !leafNode(pNode) && isItFreeNode(pNode) );
}
}
}

return 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' and 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;
}

return 0;
}