字典树

字典树是一种数据结构，可以用来进行词频统计，计算前缀个数等。它的每个节点的子节点都互不相同。

代码实现（POJ-3630）

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
using namespace std;
const int SIZE=11;
const int maxn=10010;
int t,n;
char s[maxn][20];
struct node{
    node* son[SIZE];
    bool isEnd;
    char val;
    node()
    {
        isEnd=false;
    }
} nodes[1000000];
int nodes_pos=0;
node *root;
bool insert_node(char* c)
{
    node* node1=root;
    //if(s0.length()==0)
      //  return 0;
    //const char* c=s0.c_str();
    for(int i=0;i<strlen(c);i++)
    {
        char c1=c[i];
        int pos=c1-'0';
        if(node1->son[pos]==NULL)
        {
            node* node2=&nodes[nodes_pos++];
            node2->val=c1;
            node1->son[pos]=node2;
        }else
        {
            if(node1->son[pos]->isEnd)
            {
                return 0;
            }
        }
        node1=node1->son[pos];
    }
    for(int k=0;k<SIZE;k++)
    {
        if(node1->son[k]!=NULL)
            return 0;
    }
    node1->isEnd=true;
    return 1;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        root=&nodes[nodes_pos++];
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%s",s[i]);
        }
        bool flag=true;
        for(int i=0;i<n;i++)
        {
            if(!insert_node(s[i]))
            {
                flag=false;
                break;
            }

        }
        if(flag==true)
        {
            printf("YES\n");
        }
        else
        {
            printf("NO\n");
        }
    }
    return 0;
}

需要注意的问题：

1:具有指针成员的结构体赋值时，要考虑浅拷贝的问题；
2:new结构体会出现时间问题，所以可以提前声明一个足够大的结构体数组，然后在赋值；
3:读字符串有可能会导致超时；
4:要仔细考虑各种可能出现的情况，例如：当搜索的字符串为较短的前缀时；
5:声明数组一定要声明的足够大，否则可能会出现时间错误。