学步园

trie：141MS

#include<cstdio>
const int maxn=100000+10;
const int tk=26,tb=97;
int triecnt=1,bufcnt=0,tree[maxn<<2][tk+1];
char buf[maxn<<1][12];
int search(char *s)
{
    for(int rt=0;rt=tree[rt][*s-tb];)
        if(*(++s)==0) return tree[rt][tk];
    return 0;
}
void insert(char *s,int rank=1)
{
    int rt,nxt;
    for(rt=0;*s;rt=nxt,++s)
    {
        nxt=tree[rt][*s-tb];
        if(!nxt)
            tree[rt][*s-tb]=nxt=triecnt++;
    }
    tree[rt][tk]=rank;
}
int main()
{
    int i,j;
    char str[50];
    while(gets(str)&&str[0])
    {
        char *s1=buf[bufcnt],*s2=buf[bufcnt+1];
        for(i=0;str[i]!=' ';i++)
            s1[i]=str[i];
        s1[i]=0;
        while(str[++i]==' ');
        for(j=0;str[i];i++)
            s2[j++]=str[i];
        s2[j]=0;
        insert(s2,bufcnt+1);
        bufcnt+=2;
    }
    while(gets(str)!=NULL)
    {
        int t=search(str);
        puts(t?buf[t-1]:"eh");
    }
    return 0;
}