c++ - 解决 SPOJ ww​​w.spoj.com/problems/PRHYME/的正确方法是什么？

Question

我一直在努力解决这个问题 SPOJ ww​​w.spoj.com/problems/PRHYME/?几天了，但没有成功。这是问题的简要说明:

Given is a wordlist L, and a word w. Your task is to find a word in L that forms a perfect rhyme with w. This word u is uniquely determined by these properties:

• It is in L.
• It is different from w.
• Their common suffix is as long as possible.
• Out of all words that satisfy the previous points, u is the lexicographically smallest one.

Length of a word will be<=30.
And number of words both in the dictionary and the queries can be 2,50,000.

我正在使用一个 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。

要创建 trie，可以使用以下伪代码:

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

查找单词w:

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

另一种类似的可能性是使用哈希表将所有后缀映射到两个字典序最小的单词，而不是使用 trie。如果您可以使用 std::unordered_map，这可能更容易实现。