#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

const int num_chars=26;

class Trie
{
public:
    Trie():root(NULL){}
    ~Trie();
    int search(const char* toSearch,char* entry) const;
    int insert(const char* toInsert,const char* entry);
private:
    struct TrieNode
    {
        char* data;
        TrieNode* branch[num_chars];
        TrieNode();
    };
    TrieNode* root;
};

Trie::TrieNode::TrieNode()
{
    data = NULL;
    for(int i=0;i<num_chars;++i)
        branch[i]=NULL;
}

int Trie::search(const char* toSearch,char* entry) const
{
    TrieNode* location=root;
    char char_code;
    while(location!=NULL && *toSearch!=0)
    {
        if(*toSearch>=‘A‘&&*toSearch<=‘Z‘)
            char_code=*toSearch-‘A‘;
        else if(*toSearch>=‘a‘ && *toSearch<=‘z‘)
            char_code=*toSearch-‘a‘;
        else
            return 0;
        location=location->branch[char_code];
        ++toSearch;
    }
    if(location!=NULL&& location->data !=NULL)
    {
        strcpy(entry,location->data);
        return 1;
    }
    return 0;
}

int Trie::insert(const char* toInsert,const char* entry)
{
    int result=1;
    if(root==NULL)
        root=new TrieNode();
    TrieNode* location=root;
    char char_code;
    while(location!=NULL && *toInsert !=0)
    {
        if(*toInsert>=‘A‘&&*toInsert<=‘Z‘)
            char_code=*toInsert-‘A‘;
        else if(*toInsert>=‘a‘ && *toInsert<=‘z‘)
            char_code=*toInsert-‘a‘;
        else
            return 0;
        if(location->branch[char_code]==NULL)
            location->branch[char_code]=new TrieNode();
        location=location->branch[char_code];
        ++toInsert;
    }
    if(location->data !=NULL)
        result=0;
    else
    {
        location->data=http://www.mamicode.com/new char[strlen(entry)+1];
        strcpy(location->data,entry);
    }
    return result;
}

Trie::~Trie()
{
    if(root!=NULL)
    {
        if(root->data!=NULL)
                delete  root->data;
        for(int i=0;i<num_chars;++i)
        {
            if(root->branch[i]!=NULL)
                delete root->branch[i];
        }
        delete root;
    }
    
}
int _tmain(int argc, _TCHAR* argv[])
{
    Trie t;
    char entry[100];
    t.insert("aa", "AA"); 
    t.insert("aab","BB");
    t.insert("aabc","CC"); 
    t.insert("aabbd","DD");
    t.insert("aabbdd","EE"); 
    t.insert("bba","FF");
    t.insert("bbaaa","GG"); 
    t.insert("WANGWEI", "HH");
    if (t.search("WANGWEI", entry))
        cout<<"‘WANGWEI‘ was found. pos: "<<entry<<endl;
    if (t.search("aabbdd", entry))
        cout<<"‘aabbdd‘ is found. pos: "<<entry<<endl;
    if (t.search("gg", entry))
        cout<<"‘gg‘ is found. pos: "<<entry<<endl;
    else
        cout<<"‘gg‘ does not exist at all!"<<endl;

    if (t.search("aa", entry))
        cout<<"‘aa was found. pos: "<<entry<<endl;
    return 0;
}