HDU-1251 统计难题

使用字典树(Trie)存储字符数据。在Oi-wiki上的字典树模板是：

struct trie {
  int nex[100000][26], cnt;
  bool exist[100000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int l) {  // 插入字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
      p = nex[p][c];
    }
    exist[p] = 1;
  }

  bool find(char *s, int l) {  // 查找字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
  }
};

字典树就是把一串字符串摁拆了然后以树的结构储存。在模板中，nex[p][c]，p是改节点的下标即cnt，c是字母代号，其值表示下一个节点代号。

样图中1->2的nex即为nex[1][0]=2，0的含义是a。4->9的nex即为nex[4][1]=9。

本题要求的是查找前缀，其实就是寻求树节点所支配的所有叶子。

如图所示，用Calc数组来存储改节点下的所有叶子。其实换一种想法，可以用遍历时路过该节点的次数作为此节点Calc数组。

如这个数据：

acm
ac
acj
ack
abc
abd

在这个数据的字典树Insert过程中，可以看到a走了6次，b被路过了2次，c被路过了4次。

这其实就是以a,ab,ac作为输入时的答案。

因此，需要将模板代码改成如下形式：

int nex[1000005][26],cnt;
int calc[1000005];
void insert(string str){
    int p=0;
    for(int i=0;i<str.size();i++){
        int ch=str[i]-'a';
        if(!nex[p][ch]) {
            nex[p][ch]=++cnt;
        }
        p=nex[p][ch];
        calc[p]++;//储存遍历的时候该节点路过了几次
    }
}
int find(string str){
    int p=0;
    for(int i=0;i<str.size();i++){
        int ch=str[i]-'a';
        if(!nex[p][ch]) return 0;
        p=nex[p][ch];
    }
    return calc[p];//直接返回calc值，此时exist的作用被calc代替。
}