POJ 2001

 #include<iostream>
 using namespace  std;
 const int kind=26;
 struct trienode
 {
    trienode * next[kind];    
    int branch;
    trienode()
    {
        branch=0;
        for(int i=0;i<kind;i++)
            next[i]=NULL;    
    }
};
class trie
{

    trienode * root;
public:
    trie()
    {
        root=NULL;
    }
    void insert(char s[])
    {
        trienode * location = root;
        if(location == NULL)
            location = root = new trienode();
        int i = 0,k;
        while(s[i])
        {
            k=s[i]-'a';
            if(location->next[k])
                location->next[k]->branch++;
            else
            {
                location->next[k]=new trienode();
                location->next[k]->branch++;    
            }
            i++;
            location = location->next[k];    
        }
    }
    int search(char s[]){
        trienode * location = root;
        if(!location) 
            return 0;
        int k,i = 0,ans;
        while(s[i])
        {
            k=s[i] - 'a';
            if(!location->next[k])
            return 0;
            cout<<s[i];
            ans = location->next[k]->branch;
            if(ans == 1)
                return 1;
            location = location->next[k];
            i++;
        }  
        return ans;
    }
    
};
int main()
{
    //freopen("acm.acm","r",stdin);
    char a[1000][26];
    char b[26];
    int i = 0;
    int j;
    int num;
    trie mytrie;
    while(cin>>a[i])
    {
        mytrie.insert(a[i]);
        ++ i;
    }
    for(j = 0; j < i; ++ j)
    {
        cout<<a[j]<<" ";
        mytrie.search(a[j]);
        cout<<endl;
    }
    return 0;
}