/*

trie树：

插入：

    插入一段字符串：

        每个字符作为树的一层（同一层的节点通过兄弟节点项连），每个节点如果有后继节点的话，就把最大的后继放到其后面。

        如果字符串结束，就在该节点处，connt++;然后用一个字符串指针指向实际匹配的字符串的地址。

查询：

    给定一个字符串，通过字符串和树遍历匹配，匹配到该字符串最后的一个节点时，就输出，字符串指针所指向的位置。

*/

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#define MAX 100010

typedef struct T

{

    int count;/*记录相同字符串的个数*/

    struct T * Next;/*下一层排名第1节点的地址*/

    struct T * borther;/*同一层比该节点排名后的兄弟*/

    char *real;/*实际指向的字符串*/

    char msg;/*该节点的信息*/

}Node;

typedef struct N

{

    char key[],source[];

}Element;

Element element[MAX];

void create(Node *trie)

{

    trie->count=;

    trie->Next=trie->borther=NULL;

    trie->real=NULL;

}

void insert(Node *trie,int L)

{

    int i,j,flag=,h=;

    Node *p,*s,*o,*x,*temp;

    s=p=trie;

    for(i=;i<strlen(element[L].key);i++)

    {

        if(!s->Next)/*如果上一层下面是空的，就把创建一个将当前的方进*/

        {

            o=(Node *)malloc(sizeof(Node));

            o->msg=element[L].key[i];/*该字符放入其中*/o->count=;

            o->Next=o->borther=NULL;o->real=NULL;

            s->Next=p=o;;/*将当前节点更新为上一个节点*/

        }

        else{

            h=;

            x=p=s->Next;

            while(p)

            {

                if(element[L].key[i]==p->msg){/*如果相同，那么肯定之前存在过,就找下一层*/

                    h=;break;

                }

                else if(element[L].key[i]>p->msg){/*如果排名在他前面就停止移动*/

                        x=p;

                        p=p->borther;/*如果排名比他后，往后移*/

                    }

                else {

                    if(p==s->Next)

                    {

                        h=;

                        o=(Node *)malloc(sizeof(Node));

                        o->msg=element[L].key[i];/*该字符放入其中*/o->count=;

                        o->Next=NULL;o->real=NULL;

                        s->Next=o;o->borther=p;p=o;/*将当前节点更新为上一个节点*/

                    }

                    break;

                }

            }

            if(h==)

            {

                o=(Node *)malloc(sizeof(Node));

                o->msg=element[L].key[i];/*该字符放入其中*/o->count=;

                o->Next=NULL;o->real=NULL;

                x->borther=o;o->borther=p;p=o;/*将当前节点更新为上一个节点*/

            }

        }

        if(element[L].key[i+]=='\0'){/*找到字符串的终点就返回*/

            p->real=element[L].source;p->count++;

        //    printf("%s\n",source);

            return ;

        }

        s=p;

    }

}

int serch(Node *trie,char *s)

{

    int i=;

    Node *p=trie->Next;

    while(p)

    {

        if(p->msg==s[i])

        {

            i++;

            if(s[i]=='\0') {

                printf("%s\n",p->real);return ;

            }

            else

            {

                p=p->Next;

            }

        }

        else

        p=p->borther;

    }

    return ;

}

int main(void)

{

    int i,j;

    Node trie;/*创建一个树的根节点，没用动态创建*/

    char s[*MAX];

    create(&trie);/*传递地址，初始化树的根节点的数据*/

    j=;

    while(gets(s)){

        if(strcmp(s,"\0")==)/*输入空行直接跳出*/

            break;

        for(i=;i<strlen(s);i++)/*输入字符串，将其拆分成键值对字符串*/

            if(s[i]==' '){

                s[i]='\0';

                strcpy(element[j].source,s);

                strcpy(element[j].key,&s[i+]);

                break;

            }

        insert(&trie,j);/*将值插入到树中*/

        j++;

    }

    s[]='y';

    while(gets(s)){/*输入关键字进行查询*/

        if(strcmp(s,"\0")==)/*输入空行直接跳出*/

            break;

        if(!serch(&trie,s))/*查找失败就输出eh,成功就自动输出*/

            printf("eh\n");

        s[]='y';

    }

    return ;

}