# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
struct point
{
       vector<point> next;
       char c;
       int search(char pos)
       {
            for(int i=0;i<next.size();i++)
            {
             if(next[i].c==pos) return i;
            }
            return -1;
       }
};
class dic
{
   public:
     point head;
     void insert(char *pos)
     {
          point *t=&head;
          for(int i=0;i<strlen(pos);i++)
          {
             int res;
             if((res=t->search(pos[i]-'A'))!=-1) t=&head.next[res];
             else
             {
                point temp;
                temp.c=pos[i]-'A';
                (t->next).push_back(temp);
                t=&(t->next[t->next.size()-1]);
             }
          }
     }
};  
dic refer[22];   
int map[30];
int tmap[30];
vector<char*> target;
bool flag=0;
bool hasmap[30];
bool cmp(const char *a,const char *b)
{
     return strlen(a)>strlen(b);
}
bool deal(int layer,int pos,point &t)
{
     if(layer>=target.size())
     {
        if(flag) return 1;
        else 
        {
             for(int i=0;i<26;i++) map[i]=tmap[i];
             flag=1;
             return 0;
        } 
     }
     else if(pos>=strlen(target[layer]))
     {
       if(layer+1==target.size())
       {
        point temp;
        return deal(layer+1,0,temp);
       }
       else return deal(layer+1,0,refer[strlen(target[layer+1])].head);
     }
     else
     {
         if(tmap[target[layer][pos]-'A']!=-1)
         {
           int res;
           if((res=t.search(tmap[target[layer][pos]-'A']))!=-1) return deal(layer,pos+1,t.next[res]);
           else return 0;
         }
         else
         {
             for(int i=0;i<t.next.size();i++)
             {
              if(!hasmap[t.next[i].c])
              {
               hasmap[t.next[i].c]=1;
               tmap[target[layer][pos]-'A']=t.next[i].c;
               if(deal(layer,pos+1,t.next[i])) return 1;
               hasmap[t.next[i].c]=0;
               tmap[target[layer][pos]-'A']=-1;
              }
             }
             return 0;
         }
     }
}
 void insert(char *pos)
{
     char *temp=new char[22];
     strcpy(temp,pos);
     target.push_back(temp);
}
void clear()
{
     for(int i=0;i<target.size();i++) delete[] target[i];
     target.clear();
}                
int main()
{
    int num;
    scanf("%d",&num);
    for(int i=1;i<=num;i++)
    {
       char temp[22];
       scanf("%s",temp);
       refer[strlen(temp)].insert(temp);
    }
    scanf("%d",&num);
    for(int j=0;j<26;j++) tmap[j]=-1;
    int i=1;
    char temp[100];
    getchar();
    gets(temp);
    while(i<=num)
    {
        gets(temp);
        if(!strlen(temp))
        {
         sort(target.begin(),target.end(),cmp);
         if(deal(0,0,refer[strlen(target[0])].head))
         {
           printf("#More than one solution#\n");
         }
         else if(flag)
         {
           int res[26];
           for(int j=0;j<26;j++) res[j]=-1;
           for(int j=0;j<26;j++)
             if(map[j]!=-1) res[map[j]]=j;
           for(int j=0;j<26;j++)
           {
             if(res[j]!=-1) printf("%c",res[j]+'A');
             else printf("*");
           }
           printf("\n");
         }
         else printf("#No solution#\n");             
          i++;
         for(int j=0;j<26;j++) tmap[j]=-1;
         memset(hasmap,0,sizeof(hasmap));
         clear();
         flag=0;
         continue;
        }
        char *pos;
        pos=strtok(temp," ");
        insert(pos);
        while(pos=strtok(NULL," ")) 
        {
           insert(pos);
        }
    }
      system("pause");  
}

• 附代码。 (0) yzhw9981 2009-04-10 13:50:42