Problem Description

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

Output

对于每个提问,给出以该字符串为前缀的单词的数量.

Sample Input

banana
band
bee
absolute
acm

ba
b
band
abc

Sample Output

2
3
1
0

Author

Ignatius.L

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

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代替。
}
#include <iostream>
#include <cstring>
using namespace std;
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];
}
int main(){
//    freopen("In.txt","r",stdin);
    string str;
    memset(nex,0,sizeof nex);
    while(getline(cin,str)){
        if(str=="") break;
        insert(str);
    }
    while(getline(cin,str)){
        cout << find(str) << endl;
    }
    return 0;
}