poj 2503 Babelfish (trie)

http://poj.org/problem?id=2503

思路很简单，对foreign language word建trie树，插入时一并传入word的序号，与english word相对应。查找时直接查找word标记的序号，从存储数组中输出englishword就好了。

比较蛋疼的是这题的输入，一开始真心搞不定啊。。搞定后直接1Y。

code:

#include<cstdio>
#include<cstring>
char str[100001][11] ;//模式串
char estr[100001][11] ;
#define MAX 26 //字符集大小
typedef struct TrieNode{
    int no ;
    int count ; //记录该字符出现次数
    struct TrieNode *next[MAX] ;
}TrieNode ;

TrieNode Memory[1000000] ;
int allocp = 0 ;

/*初始化*/
void InitTrieRoot(TrieNode **pRoot){
    *pRoot = NULL ;
}

/*创建新结点*/
TrieNode *CreateTrieNode(){
    int i ;
    TrieNode *p ;

    p = &Memory[allocp++] ;
    p->count = 1 ;
    for(i=0; i<MAX; i++){
        p->next[i] = NULL ;
    }
    return p ;
}

/*插入*/
void InsertTrie(TrieNode **pRoot, char *s, int no){
    int i, k ;
    TrieNode *p ;
    if(!(p=*pRoot)){
        p = *pRoot = CreateTrieNode() ;
    }
    i = 0 ;
    while(s[i]){
        k = s[i++] - 'a' ; //确定branch
        if(p->next[k]){
            p->next[k]->count ++ ;
            p->next[k]->no = no ;
        }
        else{
            p->next[k] = CreateTrieNode() ;
            p->next[k]->no = no ;
        }
        p = p->next[k] ;
    }
}

//查找
int SearchTrie(TrieNode **pRoot, char *s){
    TrieNode *p ;
    int i , k ;

    if(!(p=*pRoot))
        return -1 ;
    i = 0 ;
    while(s[i]){
        k = s[i++] - 'a' ;
        if(p->next[k]==NULL)    return -1 ;
        p = p->next[k] ;
    }
    return p->no ;
}
int main(){
    char s[11] ;
    int n = 0, i=1 ;
    allocp = 0 ;
    TrieNode *root = NULL ;
    InitTrieRoot(&root) ;
    scanf("%c", &estr[i][0]) ;
    while(scanf("%s%s", estr[i]+1, s)){
        getchar() ;
        InsertTrie(&root, s, i++) ;
        scanf("%c", &estr[i][0]) ;
        if(estr[i][0]=='\n') break ;
    }
    while(~scanf("%s", s)){
        int ans = SearchTrie(&root, s) ;
        if(ans==-1) printf("eh\n") ;
        else    printf("%s\n", estr[ans]) ;
    }
    return 0 ;}