hdu 1247 hatword(第一次写trie)

#include <iostream>
#include <string>
#define msize 50005
#define SIZE 26
#define MAXN 102400
using namespace std;
 
class Trie
{
public:
    struct node
    {
        int words;
        int prefixes;
        int edges[SIZE]; //支持26个小写英文字母
    };
    node Tree[MAXN];
    int N;
 
    void initTrie(void)
    {
        init(0);
        N = 1;
    }
    void init(int i)
    {
        Tree[i].words = 0;
        Tree[i].prefixes = 0;
        for (int j = 0; j < SIZE; j++) Tree[i].edges[j] = -1;
    }
    void addWord(int i, char* word)
    {
        if (word[0] == ‘\0‘) Tree[i].words++;
        else
        {
            Tree[i].prefixes++;
            int k = word[0] – ‘a’;
            if (Tree[i].edges[k] == -1)
            {
                Tree[i].edges[k] = N++;
                init(Tree[i].edges[k]);
            }
            addWord(Tree[i].edges[k], word + 1);
        }
    }
    int countWords(int i, char* word)
    {
        int k = word[0] – ‘a’;
        if (word[0] == ‘\0‘) return Tree[i].words;
        else if (Tree[i].edges[k] == -1) return 0;
        else return countWords(Tree[i].edges[k], word + 1);
    }
    int countPrefixes(int i, char* prefix)
    {
        int k = prefix[0] – ‘a’;
        if (prefix[0] == ‘\0‘) return Tree[i].prefixes;
        else if (Tree[i].edges[k] == -1) return 0;
        else return countPrefixes(Tree[i].edges[k], prefix + 1);
    }
};
 
char dic[msize][16];
Trie T;
 
int main()
{
    int n=6;
    T.initTrie();
    while (scanf(“%s”,dic[n])==1) T.addWord(0,dic[n]),n++;
//    for(int i=0;i<6;i++)
//    {
//         scanf(”%s”,dic[i]);
// T.addWord(0,dic[i]);
//    }
 
    for (int i=0;i<n;i++)
    {
        int m=strlen(dic[i]);
        for (int j=1;j<=m-1;j++)
        {
            char ch=dic[i][j];
            dic[i][j]=0;
            if (T.countWords(0,dic[i])==1)
            {
                dic[i][j]=ch;
                if (T.countWords(0,&dic[i][j])==1)
                {
                    printf(“%s\n“,dic[i]);
                    break;
                }
            }
            dic[i][j]=ch;
        }
    }
 
    return 0;
}