/*
字典搜索
问题描述：
给定一个字典，有若干个单词，每个单词不超过6个字母，以****作为输入结束 
要求：输入一堆乱序字母作为输入单词，比较字典中的字母，如果输入的单词经过排列组合
可以与字典中的单词匹配，则输出（如果和多个单词匹配，从小到大输出）
如果字典单词无匹配，输出:( 

样例输入：
trap given score refund only tarp work earn course pepper part ******
resco nfudre aptr seet oresuc

样例输出：
score
refund
part tarp trap
:(
course
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
#define N 7
int char_cmp(const void *,const void *);
int charpoin_cmp(const void *,const void *);
void SortDir(void *,int num,int size,int (*)(const void *,const void *));
void Prin(char **,int);
void SortDir2(char *mid,int);
int main(void)
{
    char **mid=(char **)malloc(MAX*sizeof(char *)); 
    char **sorted=(char **)malloc(MAX*sizeof(char *));
    char*   stop="****";
    char *str;
    int flag=0;
       int i=0;
    int cnt=0;
    do{
        str=(char *)malloc(N*sizeof(char));//数组储存的是指针 
        scanf("%s",str);
        mid[i]=str;
        fflush(stdin);
        i++;
    }while((strcmp(stop,mid[i-1])));
    //字典排序
    cnt=i;
    SortDir(mid,cnt-1,sizeof(char *),charpoin_cmp);
    for(i=0;i<cnt-1;i++){
        str=(char *)malloc(N*sizeof(char));
        strcpy(str,mid[i]);
        sorted[i]=str;
       SortDir(sorted[i],strlen(sorted[i]),sizeof(char),char_cmp);
      }
    //储存单词
    while(1){
        str=(char *)malloc(N*sizeof(char));
        if(scanf("%s",str)==EOF) break;
        SortDir(str,strlen(str),sizeof(char),char_cmp);
        
        for(i=0;i<cnt-1;i++){
            if(!strcmp(sorted[i],str)){
                printf("%s",mid[i]);
              flag=1;
            } 
        }//for i
        if(flag == 0){
                printf(":(");
        }//if flag
        flag=0;
        putchar('\n');
    }//while
    return 0;
}
int char_cmp(const void *a,const void *b)
{
    return *(char *)a-*(char *)b;
}
int charpoin_cmp(const void *a,const void *b)
{
    return strcmp(*(char **)a,*(char **)b); 
}
void SortDir(void *mid,int num,int size,int cmp(const void *a,const void *b))
{
    int i,j;
    int cnt;
    int min=0;
    void *temp=(void *)malloc(size);
    for(i=0;i<num-1;i++){ 
        for(min=i,j=i+1;j<num;j++){
            if(cmp(mid+min*size,mid+j*size)>0)
                min=j;
            }
            memcpy(temp,mid+i*size,size);
            memcpy(mid+i*size,mid+min*size,size);
            memcpy(mid+min*size,temp,size);
        }
}
void Prin(char **mid,int n)
{
    int i;
    for(i=0;i<n;i++){
        puts(mid[i]);
        putchar('\n');
    }
}