1 #include <iostream>
  2 #include <algorithm>
  3 using namespace std;
  4 #define M 8
  5 struct word{
  6     char str[M];
  7     struct word *nextW;
  8 };
  9 struct tree{
 10     bool isOK;
 11     word *head;
 12     struct tree *next[26]; 
 13     tree(){
 14         isOK=false;
 15         head=NULL;
 16         for(int i=0;i<26;i++)
 17             next[i]=NULL;
 18     }
 19 }*root;
 20 char endMark[M]="XXXXXX";
 21 int cmp(char a,char b){
 22     return a<=b;
 23 }
 24 int main(){
 25     freopen("in.txt","r",stdin);
 26     char temp[M],dict[M],sen[105][M];
 27     int w,num=0;
 28     root=new tree;
 29     while (scanf("%s",temp)!=EOF){
 30         if(strcmp(temp,endMark)==0)
 31             break;
 32         bool isP=false;
 33         for(int i=num-1;i>=0;i--){
 34             isP=true;
 35             if(strcmp(sen[i],temp)<0){
 36                 strcpy(sen[i+1],temp);
 37                 num++;
 38                 break;
 39             }
 40             strcpy(sen[i+1],sen[i]);
 41             if(i==0){
 42                 strcpy(sen[0],temp);
 43                 num++;
 44             }
 45         }
 46         if(!isP)
 47             strcpy(sen[num++],temp);
 48     }
 49     w=0;
 50     while (w<num){
 51         strcpy(temp,sen[w++]);
 52         strcpy(dict,temp);
 53         int i,len=strlen(temp);
 54         sort(temp,temp+len,cmp);
 55         tree *cur=root;
 56         for (i=0;i<len;i++){
 57             if(cur->next[temp[i]-'a']==NULL)
 58                 cur->next[temp[i]-'a']=new tree;
 59             cur=cur->next[temp[i]-'a'];
 60         }
 61         cur->isOK=true;
 62         if(cur->head==NULL){
 63             cur->head=new word;
 64             strcpy(cur->head->str,dict);
 65             cur->head->nextW=NULL;
 66         }
 67         else{
 68             word *p=cur->head;
 69             while (p->nextW){
 70                 p=p->nextW;
 71             }
 72             p->nextW=new word;
 73             strcpy(p->nextW->str,dict);
 74             p->nextW->nextW=NULL;
 75         }
 76     }
 77     while (scanf("%s",temp)!=EOF){
 78         if(strcmp(temp,endMark)==0)
 79             break;
 80         int i,len=strlen(temp);
 81         sort(temp,temp+len,cmp);
 82         tree *cur=root;
 83         for(i=0;i<len;i++){
 84             if(cur->next[temp[i]-'a']==NULL)
 85                 break;
 86             cur=cur->next[temp[i]-'a'];
 87         }
 88         if(i<len||!cur->isOK){
 89             puts("NOT A VALID WORD");
 90             puts("******");
 91             continue;
 92         }
 93         word *q=cur->head;
 94         while (q){
 95             printf("%s\n",q->str);
 96             q=q->nextW;
 97         }
 98         puts("******");
 99     }
100     return 0;
101 }