字典树的姿势_字典树拍扁

姿势1：静态数组形式

struct Trie  
{  
    int ch[maxnode][sigema_size],val[maxnode],sz;  
    Trie() {sz=1;memset(ch[0],0,sizeof(ch[0]));memset(val,-1,sizeof(val));}  
    void insert(bign s,int v)  
    {  
        int u=0;  
        for(int i=s.len-1;i>=max(s.len-41,0);--i)  
        {  
            int c=s.d[i];  
            if(!ch[u][c])  
            {  
                memset(ch[sz],0,sizeof(ch[sz]));  
                if(val[sz]==-1) val[sz]=v;  
                ch[u][c]=sz++;  
            }  
            u=ch[u][c];  
        }  
    }  
   
    int find(char *s)  
    {  
        int u=0;  
        for(int i=0;s[i];++i)  
        {  
            int c=s[i]-'0';  
            if(!ch[u][c]) return -1;  
            u=ch[u][c];  
        }  
        return val[u];  
    }  
};

优点：访问速度非常快。

缺点：需要预先估计整个字典树的节点个数，否则会RE。同时需要非常大的内存空间，也容易MLE。和姿势2一样，不适合字符集非常大的字典树。

姿势2：动态指针形式

struct node{
    int sum;
    node* next[26];
    node(){
        sum = 0;
        memset(next,0,sizeof(next));
    }
};
 
struct Trie{
    static const int BASE = 'a';
    node * root;
    Trie(){root = new node;}
    ~Trie(){destroy(root);}
 
    void destroy(node * cur){
        for(int i =  0 ; i < 26; ++i)
            if(cur->next[i] != NULL)
                destroy(cur->next[i]);
        delete cur;
    }
 
    void insert(char * str){
        node* cur = root;
        for(char *p = str; *p; ++p){
            int c = *p - BASE;
            if(cur->next[c] == NULL)
                cur->next[c] = new node;
            cur = cur->next[c];
            cur->sum++;
        }
    }
    int query(char * str){
        node* cur = root;
        for(char *p = str; cur != NULL && *p != 0;++p)
            cur = cur->next[*p - BASE];
        if(cur == NULL)
            return 0;
        else
            return cur->sum;
    }
};

优点：动态申请空间，不用考虑字典树的节点的个数；

缺点：访问速度比第一种慢。因为要保存指针数组，不适合非常大的字符集。

姿势3：左儿子右兄弟形式

// 字母表为全体小写字母的Trie
struct Trie {
  int head[maxnode]; // head[i]为第i个结点的左儿子编号
  int next[maxnode]; // next[i]为第i个结点的右兄弟编号
  char ch[maxnode];  // ch[i]为第i个结点上的字符
  int tot[maxnode];  // tot[i]为第i个结点为根的子树包含的叶结点总数
  int sz; // 结点总数
  long long ans; // 答案
  void clear() { sz = 1; tot[0] = head[0] = next[0] = 0; } // 初始时只有一个根结点
 
  // 插入字符串s（包括最后的'\0'），沿途更新tot
  void insert(const char *s) {
    int u = 0, v, n = strlen(s);
    tot[0]++;
    for(int i = 0; i <= n; i++) {
      // 找字符a[i]
      bool found = false;
      for(v = head[u]; v != 0; v = next[v])
        if(ch[v] == s[i]) { // 找到了
          found = true;
          break;
        }
      if(!found) {
        v = sz++; // 新建结点
        tot[v] = 0;
        ch[v] = s[i];
        next[v] = head[u];
        head[u] = v; // 插入到链表的首部
        head[v] = 0;
      }
      u = v;
      tot[u]++;
    }
  }
 
  // 统计LCP=u的所有单词两两的比较次数之和
  void dfs(int depth, int u) {
    if(head[u] == 0) // 叶结点
      ans += tot[u] * (tot[u] - 1) * depth;
    else {
      int sum = 0;
      for(int v = head[u]; v != 0; v = next[v])
        sum += tot[v] * (tot[u] - tot[v]); // 子树v中选一个串，其他子树中再选一个
      ans += sum / 2 * (2 * depth + 1); // 除以2是每种选法统计了两次
      for(int v = head[u]; v != 0; v = next[v])
        dfs(depth+1, v);
    }
  }
 
  // 统计
  long long count() {
    ans = 0;
    dfs(0, 0);
    return ans;
  }
};

这个思路是将整个字典树用链表来存。对于每个节点，用head保存它所有儿子的链表的头，即左儿子。在利用这个头，去访问他的所有其他的儿子，即右兄弟。 

姿势4：map

struct Trie{
    map<char,Trie> next;
    map<char,int> times;
 
 
    void insert(char *s){
        if(*s == 0)
            return;
         else {
            times[*s]++;
            next[*s].insert(s+1);
        }
    }
    int find(char *s){
        if(next.count(*s) == 0)
            return 0;
        else if(s[1] == 0)
            return times[*s];
        else return next[*s].find(s+1);
    }
}；

 优点：好写，在满足时间要求的情况下，代码量少。动态分配内存，不容易MLE

缺点：速度慢，找到每个元素会比数组多花费时间。