解决SPOJ www.SPOJ.com/problems/prhyme/的正确方法是什么？

Question

null

我正在用trie把字典里的所有单词都倒置起来。然后，为了解决这些查询，我按照以下方式进行：-

1. 如果trie中有单词，请将其从trie中删除。
2. 现在从根遍历trie，直到查询字符串中的字符与trie值匹配的点。让最后一个字符匹配的点为p。
3. 现在从这一点P开始，我使用DFS遍历trie，在遇到叶节点时，将形成的字符串推送到可能的结果列表。
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 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;
}

Answer 1

您的算法（使用存储所有反向单词的trie）是一个良好的开端。但它的一个问题是，对于每次查找，您必须枚举所有具有特定后缀的单词，以便找到词典中最小的一个。对于某些情况，这可能需要大量的工作。

解决这个问题的一种方法是：在每个节点（对应于每个后缀）中，存储具有该后缀的两个词典中最小的单词。在构建trie时，通过更新每个新添加叶的所有祖先节点（请参见下面的伪代码），这很容易维护。

然后，要查找单词w，从该单词对应的节点开始，在树中向上，直到到达包含w以外的子代单词的节点。然后返回存储在该节点中的词典最小的单词，或者在最小的单词等于W的情况下返回第二小的单词。

for each word:
    add word to trie
    let n be the node corresponding to the new word.
    for each ancestor a 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

let n be the node corresponding to 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:
    return n.second_smallest
else:
    return n.smallest