HDOJ 1075

我自己挺满意的，用 std::map 通不过，所以就写了个字典树~

而此题写的字典树和 getword 函数都具有很强的可重用性，您认为呢

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

template <class T>
struct node {
   T     value;
   node* next;
};

template <class T>
class trie_tree {
public:
   typedef trie_tree   type;
   typedef node<type*> child_type;
protected:
   char key;
   T*   value;
   child_type* children;
public:
   trie_tree():key('*'),value(0),children(0){}
   ~trie_tree(){
       if (value)
           delete value;
       for(child_type *p=0,*itr=children;itr;itr=p) {
           if (itr) p=itr->next;
           delete itr->value;
           delete itr;
       }
   }
   T* operator[](char* str){
       T* what=0;
       get(str,what);
       return what;
   }
   bool get(char* str, T*&what) {
       if (*str==0){
           what=value;
           return what!=0;
       } else {
           char ch=*str;
           for(child_type* itr=children;itr;itr=itr->next) {
               if ( itr->value->key==ch ) {
                   return itr->value->get(str+1, what);
               }
           }
           what=0;
           return false;
       }
       return false;
   }
   bool insert(char* str,T const& v){
       if(*str==0){
           value=new T(v);
           return true;
       } else {
           char ch=*str;
           child_type* itr;
           if(children==0) {
               children=new child_type;
               children->next=0;
               children->value=new trie_tree;
               children->value->key=ch;
           }
           for(itr=children;itr&&itr->next;itr=itr->next) {
               if ( itr->value->key==ch ) {
                   return itr->value->insert(str+1, v);
               }
           }
           if(itr->value->key!=ch){
               itr->next=new child_type;
               itr->next->value=new trie_tree;
               itr=itr->next;
               itr->next=0;
           }
           itr->value->key=ch;
           return itr->value->insert(str+1,v);
       }
   }
   bool erase(char* str){
       return false;
   }
};

inline bool accept(char ch){
   return ch>='a'&&ch<='z'||ch>='A'&&ch<='Z'||ch>='0'&&ch<='9';
}
bool getword(char* pos, char*& pos_after, char* buff) {
   if(*pos==0)
       return false;
   pos_after=pos;
   for(;*pos&&!accept(*pos);++pos) {
       *buff=*pos;
       ++buff;
   }
   *buff=0;
   if(pos!=pos_after) {
       pos_after=pos;
       return true;
   }
   for(;*pos&&accept(*pos);++pos){
       *buff=*pos;
       ++buff;
   }
   *buff=0;
   pos_after=pos;
   return true;
}

int main(){
   char   mars[16],earth[16];
   char   line[3005]="1,3,43,2, sdl!!!";
//    for(char* p=line,*p2;getword(p,p2,mars);p=p2)
//        cout<<mars<<endl;
   trie_tree<string> dic;
   scanf("%s\n",mars);//START
   for(;scanf("%s",earth)&&strcmp(earth,"END");){
       scanf("%s",mars);
       dic.insert(mars,earth);
   }
   scanf("%s\n",mars);//START
   for(;gets(line)&&strcmp(line,"END");){
       string* pstr=0;
       for(char *p=line,*p2;getword(p,p2,mars);p=p2){
           pstr=dic[mars];
           if(pstr)
               cout<<*pstr;
           else
               cout<<mars;
       }
       cout<<endl;
   }
   return 0;
}