1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int trie[30][100010]; //trie[i][N]表示以i为结点，N为子节点值的编号（初始为零）
void add(string x){
    int u = 0,num = s.length();
    for(int j = 0;j < num;j++){
        int p = s[j] - 'a';
        if(!trie[u][p])trie[u][p] = ++ idx;
        u = trie[u][p];
    }
}
int query(string s){
    int res = 0, u = 0, num = s.length();
    for(int j = 0; j < num; j++){
        int p = s[j] - 'a';
        u = trie[u][p];
        res += cnt[u];
    }
    return res;
}