Trie树入门及训练

什么叫Trie树?

Trie树即字典树。

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

（以上来自百度百科，点这里）

在我看来，Trie树是一棵26叉树（如果是统计字母的话），典型的空间换时间。那到底我们利用Trie来做什么呢？

1.统计单词

2.匹配前缀

千篇一律地需要提到其性质：

1.根节点不包含字符，除根节点外的每一个子节点都只包含一个字符。

2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串

3.每个节点的所有子节点包含的字符都不相同。

而其效率主要体现，通过公共前缀尽可能减少查找复杂度。

 

下面，没拍过字典树的同学就跟着来练习吧！很快你就有感觉了。

首先，发一个模板，我是一个从开始学习语言就写C++的人，所以我用了模板+类来写，喜欢c风格的同学也可以看看其他人共享的模板。(感觉有点长～但是相对我觉得好理解，假设你知道并且喜欢用template.)

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
using namespace std;
template<int Size>
struct trie_node
{

    bool terminable;   //表示节点为字符串的结尾
    int node;           //子节点的个数
    trie_node *child[Size]; //儿子节点
    trie_node():terminable(false), node()
    {
        memset(child,,sizeof(child)); //初始化节点
    }

};
template<int Size,typename Index>
class trie
{
public:
    //定义类名
    typedef trie_node<Size> node_type;
    typedef trie_node<Size> *link_type;

    //构造函数
    trie(Index i=Index()):index(i) { }

    void clear()   //清空函数，用于析构
    {
        clear_node(root);
        for(int i=; i<Size; i++)
            root.child[i]=;
    }
    template<typename Iterator>
    void insert(Iterator begin,Iterator end)  //插入
    {
        link_type cur= &root;//当前插入结点为根
        while(begin!=end)
        {
            if(!cur->child[index[*begin]]) //没有插入过
            {
                cur->child[index[*begin]]=new node_type;
                cur->node++;    //插入后，父亲多了一个儿子
            }
            cur=cur->child[index[*begin]]; //搜儿子
            begin++;      //迭代器往前走！
        }
        cur->terminable=true;

    }

    void insert(const char * str)  //重载c风格插入
    {
        insert(str,str+strlen(str));
    }

    template <typename Iterator>
    bool find(Iterator begin,Iterator end)    //查找
    {
        link_type cur=&root;
        while(begin!=end)
        {

            if(!cur->child[index[*begin]]) //没有节点啊！！！
                return false;
            cur=cur->child[index[*begin]]; //搜索儿子
            begin++;
        }
        return cur->terminable; //是否为字符串
    }

    bool find(const char *str)   //重载c风格
    {
        return find(str,str+strlen(str));
    }

    template<typename Iterator>
    bool earse (Iterator begin,Iterator end)     //删除字符串
    {
        bool result;
        earse_node(begin,end,root,result);
        return result;
    }

    bool erase(char *str)  //c语言风格
    {
        return earse(str,str+strlen(str));

    }

private:

    void clear_node(node_type cur)   //清空
    {
        for(int i=; i<Size; i++)
        {
            if(cur.child[i]==)continue; //不存在
            clear_node(*cur.child[i]);
            delete cur.child[i];
            cur.child[i]=;
            if(--cur.node==) break; //没有节点了

        }

    }

    //一边搜索一边删除
    template<typename Iterator>
    bool earse_node(Iterator begin ,Iterator end,node_type &cur,bool &result)
    {
        if(begin==end)
        {
            result=cur.terminable;
            cur.terminalbe=false;
            return cur.node==;

        }
        //当孩子不存在,结果假，返回假
        if(cur.child[index[*begin ]]==) return !(result=false);
        else if(earse_node(begin+,end,*(cur.child[index[*begin]]),result))
        {
            delete cur.child[index[*begin]];
            cur.child[index[*begin]]=;
            if(--cur.node==&&cur.terminable==false ) return true;

        }
        return false;

    }
    //根
    node_type root;
    //字符转索引，类似hash
    Index index;

};

class IndexClass
{
public:
    int operator[](const char key)
    {
        return key%; //一个映射

    }

};

int main()
{
    trie<,IndexClass> t;  //字母就是26,数字就是10
    t.insert("tree");       //插入
    t.insert("tea");
    t.insert("act");
    t.insert("adv");
    t.insert("ate");
    while(scanf("%s",str)!=EOF)//查找
    {
        if(t.find(str))
        {
            cout<<"find"<<endl;
        }

    }
    return ;
}

之后，怎么少得了经典的问题呢？

HDU1251（统计难题）

http://acm.hdu.edu.cn/showproblem.php?pid=1251

字典树做这些问题就是神器啊。注意统计的时候，node的处理，也就是insert和find的一些改变。

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
using namespace std;
template<int Size>
struct trie_node
{

    bool terminable;   //表示节点为字符串的结尾
    int node;           //子节点的个数
    trie_node *child[Size]; //儿子节点
    trie_node():terminable(false), node()
    {
        memset(child,,sizeof(child)); //初始化节点
    }

};
template<int Size,typename Index>
class trie
{
public:
    //定义类名
    typedef trie_node<Size> node_type;
    typedef trie_node<Size> *link_type;

    //构造函数
    trie(Index i=Index()):index(i) { }

    void clear()   //清空函数，用于析构
    {
        clear_node(root);
        for(int i=; i<Size; i++)
            root.child[i]=;
    }
    //插入
    template<typename Iterator>
    void insert(Iterator begin,Iterator end){
           link_type cur= &root;//当前插入结点为根
           while(begin!=end){
              if(cur->child[index[*begin]]){//插入过
                 cur=cur->child[index[*begin]];
                 ++(cur->node);

              }else{
                  cur->child[index[*begin]]=new node_type;    //这里这里！！！不一样！！！！
                ++(cur->child[index[*begin]]->node);
                cur=cur->child[index[*begin]];

              }

               begin++; //迭代器往前走！
           }
           cur->terminable=true;

        }

    void insert(const char * str)  //重载c风格插入
    {
        insert(str,str+strlen(str));
    }

    template <typename Iterator>
    bool find(Iterator begin,Iterator end)    //查找
    {
        link_type cur=&root;
        while(begin!=end)
        {

            if(!cur->child[index[*begin]]) //没有节点啊！！！
                return false;
            cur=cur->child[index[*begin]]; //搜索儿子
            begin++;
        }
        return cur->terminable; //是否为字符串
    }

    bool find(const char *str)   //重载c风格
    {
        return find(str,str+strlen(str));
    }
    template <typename Iterator>
        int findNum(Iterator begin,Iterator end){
             link_type cur=&root;
             while(begin!=end){

                 if(!cur->child[index[*begin]]) //没有节点啊！！！
                     return ;
                 cur=cur->child[index[*begin]];

                begin++;

             }

             return cur->node; //是否为字符串
        }
    //重载c风格
    int findNum(const char *str){

           return findNum(str,str+strlen(str));
    }

    template<typename Iterator>
    bool earse (Iterator begin,Iterator end)     //删除字符串
    {
        bool result;
        earse_node(begin,end,root,result);
        return result;
    }

    bool erase(char *str)  //c语言风格
    {
        return earse(str,str+strlen(str));

    }

private:

    void clear_node(node_type cur)   //清空
    {
        for(int i=; i<Size; i++)
        {
            if(cur.child[i]==)continue; //不存在
            clear_node(*cur.child[i]);
            delete cur.child[i];
            cur.child[i]=;
            if(--cur.node==) break; //没有节点了

        }

    }

    //一边搜索一边删除
    template<typename Iterator>
    bool earse_node(Iterator begin ,Iterator end,node_type &cur,bool &result)
    {
        if(begin==end)
        {
            result=cur.terminable;
            cur.terminalbe=false;
            return cur.node==;

        }
        //当孩子不存在,结果假，返回假
        if(cur.child[index[*begin ]]==) return !(result=false);
        else if(earse_node(begin+,end,*(cur.child[index[*begin]]),result))
        {
            delete cur.child[index[*begin]];
            cur.child[index[*begin]]=;
            if(--cur.node==&&cur.terminable==false ) return true;

        }
        return false;

    }
    //根
    node_type root;
    //字符转索引，类似hash
    Index index;

};

class IndexClass
{
public:
    int operator[](const char key)
    {
        return key%; //一个映射

    }

};

int main(){
    trie<,IndexClass> t;
   char s[];

    while(gets(s) && s[])
    {
        t.insert( s);
    }

    while(gets(s))
    {
        printf("%d\n", t.findNum(s));
    }

    return ;

}

HDU1671

http://acm.hdu.edu.cn/showproblem.php?pid=1671

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<vector>
using namespace std;
#define MAXN 10
template<int Size>
struct trie_node
{

    bool terminable; //表示节点为字符串的结尾
    int node;       //子节点的个数
    trie_node *child[Size]; //儿子节点
    trie_node():terminable(false), node()
    {
        memset(child,,sizeof(child)); //初始化节点
    }

};
template<int Size,typename Index>
class trie
{
public:
    //定义类名
    typedef trie_node<Size> node_type;
    typedef trie_node<Size> *link_type;

    //构造函数
    trie(Index i=Index()):index(i) { }

    //清空函数，用于析构
    void clear()
    {
        clear_node(root);
        for(int i=; i<Size; i++)
            root.child[i]=;
    }
    //插入
    template<typename Iterator>
    void insert(Iterator begin,Iterator end)
    {
        link_type cur= &root;//当前插入结点为根
        while(begin!=end)
        {
            if(cur->child[index[*begin]]) //插入过
            {
                cur=cur->child[index[*begin]];
                cur->node++;

            }
            else
            {
                cur->child[index[*begin]]=new node_type;
                cur->child[index[*begin]]->node++;
                cur=cur->child[index[*begin]];

            }
            begin++; //迭代器往前走！
        }
        cur->terminable=true;

    }

    //重载c风格插入
    void insert(const char * str)
    {
        insert(str,str+strlen(str));
    }
    //插入
    template<typename Iterator>
    bool insert2(Iterator begin,Iterator end)
    {
        link_type cur= &root;//当前插入结点为根

         bool flag=;
        while(begin!=end)
        {
            if(cur->child[index[*begin]]) //插入过
            {
                if(cur->child[index[*begin]]->terminable==true){

                    flag=;
                }
                cur=cur->child[index[*begin]];
                cur->node++;

            }
            else
            {
                cur->child[index[*begin]]=new node_type;
                cur->child[index[*begin]]->node++;
                cur=cur->child[index[*begin]];

            }
            begin++; //迭代器往前走！
        }
        cur->terminable=true;
        return flag;

    }

    //重载c风格插入
    bool insert2(const char * str)
    {
        return insert2(str,str+strlen(str));
    }

    //查找
    template <typename Iterator>
    bool find(Iterator begin,Iterator end)
    {
        link_type cur=&root;
        while(begin!=end)
        {

            if(!cur->child[index[*begin]]) //没有节点啊！！！
                return false;
            cur=cur->child[index[*begin]];

            begin++;

        }
        return cur->terminable; //是否为字符串
    }
    //重载c风格
    bool find(const char *str)
    {

        return find(str,str+strlen(str));
    }

    //查找节点数目
    template <typename Iterator>
    int findNum(Iterator begin,Iterator end)
    {
        link_type cur=&root;
        while(begin!=end)
        {

            if(!cur->child[index[*begin]]) //没有节点啊！！！
                return ;
            cur=cur->child[index[*begin]];

            begin++;

        }

        return cur->node; //是否为字符串
    }
    //重载c风格
    int findNum(const char *str)
    {

        return findNum(str,str+strlen(str));
    }

    //查找前缀
     template <typename Iterator>
    bool findPre(Iterator begin,Iterator end)
    {
        link_type cur=&root;
        while(begin!=end)
        {

            if(!cur->child[index[*begin]]) //没有节点啊！！！
                return false;

            if(cur->terminable) break;
            cur=cur->child[index[*begin]];

            begin++;

        }
        return begin!=end; //是否为字符串
    }

    bool findPre(const char *str){
        return findPre(str,str+strlen(str));

    }

    //删除字符串
    template<typename Iterator>
    bool earse (Iterator begin,Iterator end)
    {
        bool result;
        earse_node(begin,end,root,result);
        return result;

    }

    //c语言风格
    bool erase(char *str)
    {
        return earse(str,str+strlen(str));

    }

    template<typename Functor>
    void traverse(Functor &execute =Functor())
    {
        visit_node(root,execute);

    }
private:
    //访问结点
    template<typename Functor>
    void visit_node(node_type cur,Functor &execute)
    {
        execute(cur);
        for(int i=; i<Size; i++) //dfs
        {
            if(cur.child[i]==) continue;
            visit_node(*cur.child[i],execute);

        }
    }

    //清空
    void clear_node(node_type cur)
    {
        for(int i=; i<Size; i++)
        {
            if(cur.child[i]==)continue; //不存在
            clear_node(*cur.child[i]);
            delete cur.child[i];
            cur.child[i]=;
            if(--cur.node==) break; //没有节点了

        }

    }

    //一边搜索一边删除
    template<typename Iterator>
    bool earse_node(Iterator begin ,Iterator end,node_type &cur,bool &result)
    {
        if(begin==end)
        {
            result=cur.terminable;
            cur.terminalbe=false;
            return cur.node==;

        }
        //当孩子不存在,结果假，返回假
        if(cur.child[index[*begin ]]==) return !(result=false);
        else if(earse_node(begin+,end,*(cur.child[index[*begin]]),result))
        {
            delete cur.child[index[*begin]];
            cur.child[index[*begin]]=;
            if(--cur.node==&&cur.terminable==false ) return true;

        }
        return false;

    }
    //根
    node_type root;

    //字符转索引，类似hash
    Index index;

};

class IndexClass
{
public:
    int operator[](const char key)
    {
        return key%MAXN; //一个映射

    }

};

char s[][];
int main()
{
    trie<MAXN,IndexClass> t;

    int T,n,i;
  //  freopen("in.txt","r",stdin);
    scanf("%d",&T);

    while(T--)
    {
        scanf("%d",&n);

        t.clear();
        for(i=;i<n;i++){

            scanf("%s",s[i]);

            t.insert(s[i]);

        }
        for(i=;i<n;i++){

            if(t.findPre(s[i])){

                puts("NO");
                break;
            }
        }
        if(i==n) puts("YES");

    }

    return ;

}

 

HDU1004，或许你用map水过去了，但是你不妨试试用字典树获取0ms吧！

http://acm.hdu.edu.cn/showproblem.php?pid=1004

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
using namespace std;
template<int Size>
struct trie_node{

  bool terminable; //???????????
  int node;       //??????
  int cnt;
  trie_node *child[Size]; //????
  trie_node():terminable(false), node(),cnt(){
      memset(child,,sizeof(child)); //?????
  }

};
int maxN;
char sb[];
 char s[];
template<int Size,typename Index>
class trie{
    public:
        //????
        typedef trie_node<Size> node_type;
        typedef trie_node<Size> *link_type;

        //????
        trie(Index i=Index()):index(i){ }

        //????,????
        void clear(){
          clear_node(root);
          for(int i=;i<Size;i++)
              root.child[i]=;
        }
        //??
        template<typename Iterator>
        bool insert(Iterator begin,Iterator end){
           link_type cur= &root;//????????
           while(begin!=end){
              if(!cur->child[index[*begin]]){//???

                  cur->child[index[*begin]]=new node_type;

                  cur->node++;

              }
              cur=cur->child[index[*begin]];

               begin++; //??????!
           }

           cur->terminable=true;
           cur->cnt++;
           if(cur->cnt> maxN){
              maxN=cur->cnt;
             // cout<<maxN;
             return true;
           }
           return false;

        }

        //??c????
        void insert( char * str){
            if(insert(str,str+strlen(str))){
                strcpy(sb,str);

            };
        }

    private:

       //??
       void clear_node(node_type cur){
          for(int i=;i<Size;i++){
             if(cur.child[i]==)continue; //???
             clear_node(*cur.child[i]);
             delete cur.child[i];
             cur.child[i]=;
             if(--cur.node==) break; //?????

          }

       }

       //?
       node_type root;
       //?????,??hash
       Index index;

};

class IndexClass{
    public:
        int operator[](const char key){
            return key%; //????

        }

};

int main(){
    trie<,IndexClass> t;

    //freopen("in.txt","r",stdin);
    int n;
    while(scanf("%d",&n)&&n)
    {

        maxN=-;
        for(int i=;i<n;i++){
          scanf("%s",s);

          t.insert(s);
         // cout<<maxN<<endl;
        }

        printf("%s\n",sb);
        t.clear();
    }

    return ;

}

HDU1075

http://acm.hdu.edu.cn/showproblem.php?pid=1075

这题目还是很赤裸的字典树，但是我犯了一个小错，让我WA无数次。

AC的：

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
using namespace std;
char str1[];
char str2[];
char st[];

template<int Size>
struct trie_node
{

    bool terminable; //表示节点为字符串的结尾
    int node;       //子节点的个数
    char str[];
    trie_node *child[Size]; //儿子节点
    trie_node():terminable(false), node()
    {
        memset(child,,sizeof(child)); //初始化节点
    }

};

template<int Size,typename Index>
class trie
{
public:
    //定义类名
    typedef trie_node<Size> node_type;
    typedef trie_node<Size> *link_type;

    //构造函数
    trie(Index i=Index()):index(i) { }

    //清空函数，用于析构
    void clear()
    {
        clear_node(root);
        for(int i=; i<Size; i++)
            root.child[i]=;
    }
    //插入
    template<typename Iterator>
    void insert(Iterator begin,Iterator end)
    {
        link_type cur= &root;//当前插入结点为根
        while(begin!=end)
        {
            if(cur->child[index[*begin]]) //插入过
            {
                cur=cur->child[index[*begin]];
                ++(cur->node);

            }
            else
            {
                cur->child[index[*begin]]=new node_type;
                ++(cur->child[index[*begin]]->node);
                cur=cur->child[index[*begin]];

            }

            begin++; //迭代器往前走！
        }
        cur->terminable=true;
        int len=strlen(str1);
        for(int i=; i<=len; i++)
            cur->str[i]=str1[i];

    }

    //重载c风格插入
    void insert(const char * str)
    {
        insert(str,str+strlen(str));
    }

    //查找
    template <typename Iterator>
    bool find(Iterator begin,Iterator end)
    {
        link_type cur=&root;
        while(begin!=end)
        {

            if(!cur->child[index[*begin]]) //没有节点啊！！！
                return false;
            cur=cur->child[index[*begin]];

            begin++;

        }
        //     printf("%s sb",cur->str);
        if(cur->terminable)
        {
            printf("%s",cur->str);
            return true;

        }
        return false; //是否为字符串
    }

    //重载c风格
    bool find(const char *str)
    {

        return find(str,str+strlen(str));
    }

private:

    //清空
    void clear_node(node_type cur)
    {
        for(int i=; i<Size; i++)
        {
            if(cur.child[i]==)continue; //不存在
            clear_node(*cur.child[i]);
            delete cur.childe[i];
            cur.child[i]=;
            if(--cur.node==) break; //没有节点了

        }

    }

    //根
    node_type root;
    //字符转索引，类似hash
    Index index;

};

class IndexClass
{
public:
    int operator[](const char key)
    {
        return key%; //一个映射

    }

};

int main()
{
    trie<,IndexClass> t;
    scanf("%s",str2) ;

    while(scanf("%s",str1))
    {
        if(str1[]=='E')
        {

            break;
        }
        scanf("%s",str2);
        t.insert(str2);
    }
    scanf("%s",str2);

    getchar();

    while(gets(st))
    {

        if(st[]=='E')
        {

            break;
        }
        int len=strlen(st);
        int bg=;
        for(int i=; i<len; i++)
        {
            if(st[i]>='a'&&st[i]<='z')
            {

                continue;
            }
            if(!t.find(st+bg,st+i))
            {
                for(int j=bg; j<i; j++)
                  printf("%c",st[j]);

            };
            if(st[i]) printf("%c",st[i]);
            bg=i+;

        }

        puts("");

    }

    return ;

}

WA的：

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
using namespace std;
char str1[];
char str2[];
char st[];

template<int Size>
struct trie_node
{

    bool terminable; //表示节点为字符串的结尾
    int node;       //子节点的个数
    char str[];
    trie_node *child[Size]; //儿子节点
    trie_node():terminable(false), node()
    {
        memset(child,,sizeof(child)); //初始化节点
    }

};

template<int Size,typename Index>
class trie
{
public:
    //定义类名
    typedef trie_node<Size> node_type;
    typedef trie_node<Size> *link_type;

    //构造函数
    trie(Index i=Index()):index(i) { }

    //清空函数，用于析构
    void clear()
    {
        clear_node(root);
        for(int i=; i<Size; i++)
            root.child[i]=;
    }
    //插入
    template<typename Iterator>
    void insert(Iterator begin,Iterator end)
    {
        link_type cur= &root;//当前插入结点为根
        while(begin!=end)
        {
            if(cur->child[index[*begin]]) //插入过
            {
                cur=cur->child[index[*begin]];
                ++(cur->node);

            }
            else
            {
                cur->child[index[*begin]]=new node_type;
                ++(cur->child[index[*begin]]->node);
                cur=cur->child[index[*begin]];

            }

            begin++; //迭代器往前走！
        }
        cur->terminable=true;
        int len=strlen(str1);
        for(int i=; i<len; i++)
            cur->str[i]=str1[i];

    }

    //重载c风格插入
    void insert(const char * str)
    {
        insert(str,str+strlen(str));
    }

    //查找
    template <typename Iterator>
    bool find(Iterator begin,Iterator end)
    {
        link_type cur=&root;
        while(begin!=end)
        {

            if(!cur->child[index[*begin]]) //没有节点啊！！！
                return false;
            cur=cur->child[index[*begin]];

            begin++;

        }
        //     printf("%s sb",cur->str);
        if(cur->terminable)
        {
            printf("%s",cur->str);
            return true;

        }
        return false; //是否为字符串
    }

    //重载c风格
    bool find(const char *str)
    {

        return find(str,str+strlen(str));
    }

private:

    //清空
    void clear_node(node_type cur)
    {
        for(int i=; i<Size; i++)
        {
            if(cur.child[i]==)continue; //不存在
            clear_node(*cur.child[i]);
            delete cur.childe[i];
            cur.child[i]=;
            if(--cur.node==) break; //没有节点了

        }

    }

    //根
    node_type root;
    //字符转索引，类似hash
    Index index;

};

class IndexClass
{
public:
    int operator[](const char key)
    {
        return key%; //一个映射

    }

};

int main()
{
    trie<,IndexClass> t;
    scanf("%s",str2) ;

    while(scanf("%s",str1))
    {
        if(str1[]=='E')
        {

            break;
        }
        scanf("%s",str2);
        t.insert(str2);
    }
    scanf("%s",str2);

    getchar();

    while(gets(st))
    {

        if(st[]=='E')
        {

            break;
        }
        int len=strlen(st);
        int bg=;
        for(int i=; i<len; i++)
        {
            if(st[i]>='a'&&st[i]<='z')
            {

                continue;
            }
            if(!t.find(st+bg,st+i))
            {
                for(int j=bg; j<i; j++)
                  printf("%c",st[j]);

            };
            if(st[i]) printf("%c",st[i]);
            bg=i+;

        }

        puts("");

    }

    return ;

}

（差别就在字符串copy 上没有拷贝上'\0'……，也就是st[len]）

HDU1247

http://acm.hdu.edu.cn/showproblem.php?pid=1247

题目相对理解上会有点偏差,不是当且仅当两个，是两个，举个例子

a

abc

b

bc

c

输出的是:abc,bc(注意abc也是，不要因为abc=a+b+c，而忽略，只要可以满足s=s1+s2即可，即abc=a+bc，bc=b+c)

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
template<int Size>
struct trie_node{

  bool terminable; //表示节点为字符串的结尾
  int node;       //子节点的个数

  trie_node *child[Size]; //儿子节点
  trie_node():terminable(false), node(){
      memset(child,,sizeof(child)); //初始化节点
  }

};

template<int Size,typename Index>
class trie{
    public:
        //定义类名
        typedef trie_node<Size> node_type;
        typedef trie_node<Size> *link_type;

        //构造函数
        trie(Index i=Index()):index(i){ }

        //清空函数，用于析构
        void clear(){
          clear_node(root);
          for(int i=;i<Size;i++)
              root.child[i]=;
        }
        //插入
        template<typename Iterator>
        void insert(Iterator begin,Iterator end){

           link_type cur= &root;//当前插入结点为根
           while(begin!=end){
              if(cur->child[index[*begin]]){//插入过
                 cur=cur->child[index[*begin]];
                 ++(cur->node);

              }else{
                  cur->child[index[*begin]]=new node_type;
                ++(cur->child[index[*begin]]->node);
                cur=cur->child[index[*begin]];

              }

              // cout<<*begin;
               begin++; //迭代器往前走！
           }
           cur->terminable=true;

          // cout<<cur->id<<endl;

        }

        //重载c风格插入
        void insert(const char * str){
           insert(str,str+strlen(str));
        }

        //查找
        template <typename Iterator>
       bool find(Iterator begin,Iterator end){
             link_type cur=&root;

             while(begin!=end){

                if(!cur->child[index[*begin]])return false;  //我在这里re了无数次…忧桑……

                 cur=cur->child[index[*begin]];

                begin++;

             }
          //    cout<<*begin<<" "<<*end<<"sb" <<endl;
            return cur->terminable;

        }

        //重载c风格
          bool  find(const char *str){

           return  find(str,str+strlen(str));
        }

    private:

       //清空
       void clear_node(node_type cur){
          for(int i=;i<Size;i++){
             if(cur.child[i]==)continue; //不存在
             clear_node(*cur.child[i]);
             delete cur.childe[i];
             cur.child[i]=;
             if(--cur.node==) break; //没有节点了

          }

       }

       //根
       node_type root;
       //字符转索引，类似hash
       Index index;

};

class IndexClass{
    public:
        int operator[](const char key){
            return key%; //一个映射

        }

};
char str[][];

int main(){
    trie<,IndexClass> t;
    int i=;

    while(scanf("%s",str[i])!=EOF){
          //  cout<<str[i];
        t.insert(str[i]);
        i++;
    }

    for(int j=;j<i;j++){

           int len=strlen(str[j]);
         for(int p=;p<=len-;p++){

          if(t.find(str[j],str[j]+p)){

              if(t.find(str[j]+p)){

                printf("%s\n",str[j]);
                break;
              }

          }

       }

    }

    return ;

}

尽管我上面这个做法已经OK了，但是这是参考了别人，下面是我完全按自己想法写的，程序员最高兴的莫过于可以将自己的想法实现。

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
template<int Size>
struct trie_node{

  bool terminable; //表示节点为字符串的结尾
  int node;       //子节点的个数

  trie_node *child[Size]; //儿子节点
  trie_node():terminable(false), node(){
      memset(child,,sizeof(child)); //初始化节点
  }

};

template<int Size,typename Index>
class trie{
    public:
        //定义类名
        typedef trie_node<Size> node_type;
        typedef trie_node<Size> *link_type;

        //构造函数
        trie(Index i=Index()):index(i){ }

        //清空函数，用于析构
        void clear(){
          clear_node(root);
          for(int i=;i<Size;i++)
              root.child[i]=;
        }
        //插入
        template<typename Iterator>
        void insert(Iterator begin,Iterator end){

           link_type cur= &root;//当前插入结点为根
           while(begin!=end){
              if(cur->child[index[*begin]]){//插入过
                 cur=cur->child[index[*begin]];
                 ++(cur->node);

              }else{
                  cur->child[index[*begin]]=new node_type;
                ++(cur->child[index[*begin]]->node);
                cur=cur->child[index[*begin]];

              }

              // cout<<*begin;
               begin++; //迭代器往前走！
           }
           cur->terminable=true;

          // cout<<cur->id<<endl;

        }

        //重载c风格插入
        void insert(const char * str){
           insert(str,str+strlen(str));
        }

        //查找
        template <typename Iterator>
       bool find(Iterator begin,Iterator end,int i){
             link_type cur=&root;

             while(begin!=end){

                if(cur->terminable){
                    if(i>) return false;
                    if( find(begin,end,i+))return true;
                }

                if(!cur->child[index[*begin]]) return false;
                 cur=cur->child[index[*begin]];

                begin++;

             }
             if(!cur->terminable){
                 return false;
             }
            return i==;

        }

        //重载c风格
          bool  find(const char *str,int i){

           return  find(str,str+strlen(str),i);
        }

    private:

       //清空
       void clear_node(node_type cur){
          for(int i=;i<Size;i++){
             if(cur.child[i]==)continue; //不存在
             clear_node(*cur.child[i]);
             delete cur.child[i];
             cur.child[i]=;
             if(--cur.node==) break; //没有节点了

          }

       }

       //根
       node_type root;
       //字符转索引，类似hash
       Index index;

};

class IndexClass{
    public:
        int operator[](const char key){
            return key%; //一个映射

        }

};
char str[][];

int main(){
    trie<,IndexClass> t;
    int i=;
   //freopen("in.txt","r",stdin);
    while(scanf("%s",str[i])!=EOF){
          //  cout<<str[i];
        t.insert(str[i]);
        i++;
    }

    for(int j=;j<i;j++){

        if(t.find(str[j],)){ //类似与dfss

        printf("%s\n",str[j]);
       }

    }

    return ;

}

HDU1857,逆向思维的trie，可以参考我之前写过的,点这里

http://acm.hdu.edu.cn/showproblem.php?pid=1857

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
template<int Size>
struct trie_node{

    bool terminable; //表示节点为字符串的结尾
    int node; //子节点的个数
    int id;
    trie_node *child[Size]; //儿子节点
    trie_node():terminable(false), node(){
        memset(child,,sizeof(child)); //初始化节点
    }

};
int RR[],CC[];
template<int Size,typename Index>
class trie{
public:
    //定义类名
    typedef trie_node<Size> node_type;
    typedef trie_node<Size> *link_type;

    //构造函数
    trie(Index i=Index()):index(i){ }

    //清空函数，用于析构
    void clear(){
        clear_node(root);
        for(int i=;i<Size;i++)
            root.child[i]=;
    }
    //插入
    template<typename Iterator>
        void insert(Iterator begin,Iterator end,int i){

        link_type cur= &root;//当前插入结点为根
        while(begin!=end){
            if(cur->child[index[*begin]]){//插入过
                cur=cur->child[index[*begin]];
                ++(cur->node);

            }else{
                cur->child[index[*begin]]=new node_type;
                ++(cur->child[index[*begin]]->node);
                cur=cur->child[index[*begin]];

            }

            begin++; //迭代器往前走！
        }
        cur->terminable=true;
        cur->id=i;

    }

    //重载c风格插入
    void insert(const char * str,int i){
        insert(str,str+strlen(str), i);
    }

    //查找
    template <typename Iterator>
        void find(Iterator begin,Iterator end,int r,int c){
        link_type cur=&root;
        while(begin!=end){

            if(cur->terminable){

                if(RR[cur->id]==){

                    RR[cur->id]=r;
                    CC[cur->id]=c;
                }
            }

            if(!cur->child[index[*begin]]) //没有节点啊！！！
                return ;

            cur=cur->child[index[*begin]];

            begin++;

        }
        if( cur->terminable) {//是否为字符串

            if(RR[cur->id]==){

                RR[cur->id]=r;
                CC[cur->id]=c;
            }
        }

    }

    //重载c风格
    void find(const char *str,int r,int c){

        find(str,str+strlen(str),r,c);
    }

private:

    //清空
    void clear_node(node_type cur){
        for(int i=;i<Size;i++){
            if(cur.child[i]==)continue; //不存在
            clear_node(*cur.child[i]);
            delete cur.childe[i];
            cur.child[i]=;
            if(--cur.node==) break; //没有节点了

        }

    }

    //根
    node_type root;
    //字符转索引，类似hash
    Index index;

};

class IndexClass{
public:
    int operator[](const char key){
        return key%; //一个映射

    }

};
char cc[][];
char s[];
int mini(int a,int b){
    return a>b?b:a;
}
int main(){
    trie<,IndexClass> t;
    int R,C,i,j,l,ed;
    scanf("%d%d",&R,&C);
    getchar(); //读掉回车
    for( i=;i<R;i++)
    {

        gets(cc[i]);
    }

    int N=;
    while(gets(s)&&s[]!='-'){
        if(s[]){
            t.insert(s,N);   //用每一个要查找的单词构树
                N++;
        }

    }

        for(i=;i<R;i++)
            for( j=;j<C;j++){
                //向下
                memset(s,,sizeof(s));
                if(i+<R) ed=;
                else ed=R-i;
                for(l=;l<ed;l++){
                    s[l]=cc[i+l][j];

                }

                t.find(s,i+,j+);
                //向右
                memset(s,,sizeof(s));
                if(j+<C) ed=;
                else ed=C-j;
                for( l=;l<ed;l++){
                    s[l]=cc[i][j+l];

                }

                t.find(s,i+,j+);

                //右下
                memset(s,,sizeof(s));
                if(i+<R&&j+<C) ed=;
                else ed=mini(C-j,R-i);
                for( l=;l<ed;l++){
                    s[l]=cc[i+l][j+l];

                }

                t.find(s,i+,j+);

            }

            for( i=;i<N;i++){

                if(RR[i]!=||CC[i]!=)
                    printf("%d %d\n",RR[i]-,CC[i]-);
                else puts("-1 -1");
            }

            return ;

}