学步园

这道题目就是裸的Trie树，当然了也可以用其他方法做。这里为了训练的目的用Trie树做。就是这道题的输入让人蛋疼。Orz

下面是代码，哈哈自己写的Trie的模板。

#include<stdio.h>
#include<string.h>
#define maxn 200010

struct node
{
    char val[11];
    int ok;
} Val[maxn];
int ch[maxn][26];
char s1[11],s2[11],s[25];
int cnt;
void insert_Trie(char *s1,char *s2)
{
    int u = 0;
    while(*s1)
    {
        int id = *s1 - 'a';
        if(ch[u][id] == 0)
        {
            Val[cnt].ok = 0;
            ch[u][id] = cnt++;
        }
        u = ch[u][id];
        s1++;
    }
    Val[u].ok = 1;
    strcpy(Val[u].val,s2);
}
void query_Trie(char *s)
{
    int u = 0;
    int ok = 1;
    while(*s)
    {
        int id = *s - 'a';
        if(ch[u][id] == 0)
        {
            ok = 0;
            break;
        }
        u = ch[u][id];
        s++;
    }
    if(ok && Val[u].ok)
        printf("%s\n",Val[u].val);
    else
        printf("eh\n");
}
int main()
{
    cnt = 1;
    memset(ch[0],0,sizeof(ch[0]));
    while(gets(s) && s[0] != 0)
    {
        int i,j;
        for(i = 0 ; s[i] != ' ';i++)
            s1[i] = s[i];
        s1[i] = '\0';
        for(j = 0, i += 1;s[i];i++,j++)
            s2[j] = s[i];
        s2[j] = '\0';
        insert_Trie(s2,s1);
    }
    while(scanf("%s",s1) != EOF) query_Trie(s1);
    return 0;
}