字典树模板

#include <cstdio>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1000010;
const int SIZE = 26;

int ch[N][SIZE]; 
int val[N],sz;
int ans;

void init()  // 初始化
{
    sz = 1; // 标号
    memset(ch,0,sizeof(ch)); 
    memset(val,0,sizeof(val));
}
// 字典树中，对于每一个串在放进到树上时，当前串中的每一个字符都有一个编号，对于字符来说是存放到边上的。
// 所有的串的根都是一个空的，并且都是同一个
// 对于 val[N] 数组来说，是用来统计当前前缀的个数。‘
// 这里 val[u]++ 为什么会不造成覆盖问题？比如 abc 和 dbc，前缀不相同，但是在保存 val 时，都是第二个，但是这里是保存在不同的 u 里面的
// 因为 ch[u][c] = sz ++ ，标号发生了变化， 然后 u = ch[u][c]; val[u] ++; 这样就保证了统计的是不同的前缀的都放到了不同的 val 里面
void creat(char *s) // 插入单个字符
{
    int u = 0, len = strlen(s); 
    for(int i = 0; i < len; i ++)
    {
        int c = s[i] - 'a'; 
        if(!ch[u][c]) ch[u][c] = sz++;  
        u = ch[u][c];
        val[u] ++;
    }
}
// 查询前缀个数
// 查询过程中，如果 ch[u][c] == 0 ，表示没有
// 否则继续沿树向下走
int query(char *s)
{
    int u = 0, len = strlen(s);
    for(int i = 0; i < len; i ++)
    {
        int c = s[i] - 'a';
        if(!ch[u][c]) return 0;
        u = ch[u][c];
    }
    return val[u];
}
char s[100005];
int main()
{
    int n,q;
    while(~scanf("%d %d", &n, &q))
    {
        init();
        for(int i = 0; i < n ; i ++)
        {
            getchar();
            scanf("%s", s);
            creat(s);
        }
        while(q--)
        {
            getchar();
            scanf("%s", s);
            printf("%d\n",query(s));
        }
    }
    return 0;
}