C++字典树tire模版

以下是C++的字典树（Trie）模板：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 26;
int n, m;
int son[N][M], idx;
bool is_end[N];
char str[N];

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if (!son[p][u])
            son[p][u] = ++idx;
        p = son[p][u];
    }
    is_end[p] = true;
}

bool find()
{
    int p = 0;
    for (int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if (!son[p][u])
            return false;
        p = son[p][u];
    }
    return is_end[p];
}

int main()
{
    cin >> n >> m;
    while (n--)
    {
        scanf("%s", str);
        insert();
    }
    while (m--)
    {
        scanf("%s", str);
        if (find())
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

在这个模板中，我们使用一个整数数组son来表示每个节点的子节点。我们还使用一个bool数组is_end来表示从根节点到当前节点的路径是否为一个单词。

在insert函数中，我们遍历输入的字符串，并检查该字符的子节点是否存在，如果不存在，我们就创建一个新的子节点。最后，我们将当前节点标记为一个单词的结尾。

在find函数中，我们遍历查询字符串，并检查是否存在该字符的子节点。如果当前字符的子节点不存在，则该字符串不在字典树中。最后，我们检查当前节点是否标记为一个单词的结尾。如果是，我们返回true，否则返回false。

这个模板的时间复杂度为O(nm)，其中n是字典树中单词的数量，m是查询的数量。由于每个单词的长度为O(k)，因此总运行时间为O(k(n+m))，其中k是单词的平均长度。