私はこの問題を解決しようとしていますSPOJwww.spoj.com/problems/PRHYME/？数日間、しかし成功していません。ここに簡単な問題があります：
与えられたのは単語リストLと単語wです。あなたの仕事は、wと完璧な韻を踏むLの単語を見つけることです。この単語uは、次のプロパティによって一意に決定されます。
- Lにあります。
- wとは違います。
- それらの共通の接尾辞は可能な限り長くなります。
- 前のポイントを満たすすべての単語の中で、uは辞書式順序で最小の単語です。
単語の長さは<=30になります。
また、辞書とクエリの両方の単語数は250,000になります。
私はトライを使用して、辞書のすべての単語を逆に保存しています。次に、クエリを解決するために、次のように進めます。-
- 単語がトライに存在する場合は、トライから削除します。
- 次に、ルートから、クエリ文字列の文字がトライ値と一致するポイントまでトライをトラバースします。最後の文字一致が見つかったこのポイントをPとします。
- ここで、この時点からP以降、DFSを使用してトライをトラバースし、リーフノードに遭遇したら、形成された文字列を可能な結果リストにプッシュします。
- ここで、このリストから辞書式順序で最小の結果を返します。
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 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;
}
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;
}