Trie解決POJ 2503

  ：http://poj.org/problem?id=2503
            ，    。 

 
  
 
    
    
   View Code  
   
 
    
#include "iostream"

using namespace std;



typedef struct node{

    char word[21];

    int mark;

    struct node * next[26];

}node;

node * root;

void InitRoot(){

    root = new node();

    root->mark=0;

    memset(root->next, NULL, sizeof(root->next));

}

void Build(char *key, char *val){

    node *p = root;

    int i, k, len = strlen(key);

    for(i=0; i<len; i++){

        k = key[i]-'a';

        if(p->next[k]==NULL){

            p->next[k] = new node();

            p->next[k]->mark = 0;

            strcpy(p->word, "");

            //       p->next[k]->next,          

            memset(p->next[k]->next, NULL, sizeof(p->next[k]->next));

        }

        p = p->next[k];

        if(i==len-1){

            p->mark = 1;

            strcpy(p->word, val);

        }

    }

}

void Find(char *key){

    int i, j, k, len = strlen(key);

    node *p = root;

    for(i=0; i<len; i++){

        k = key[i]-'a';

        p = p->next[k];

        if(p==NULL){

            cout<<"eh"<<endl;

            break;

        }

        if(i==len-1){

            if(p->mark==1){

                cout<<p->word<<endl;

            }else{

                cout<<"eh"<<endl;

            }

        }

    }

}

int main(){

    char str[21], val[21], key[21];

    InitRoot();

    while(gets(str)&&str[0]){

        sscanf(str, "%s%s", val, key);

        Build(key, val);

    }

    while(scanf("%s", str)!=EOF){

        Find(str);

    }

    return 0;

}