trie树

Trie一般指字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

对于字典树，有三个重要性质： 1：根节点不包含字符，除了根节点，每个节点都只包含一个字符。root 节点不包含字符，这样做的目的是为了能够包括所有字符串。 2：从根节点到某一个节点，路过字符串起来就是该节点对应的字符串。 3：每个节点的子节点字符不同，也就是找到对应单词、字符是唯一的。

#include <bits/stdc++.h>
using namespace std;

class Trie {
    struct node {
        int cnt;
        node* next[26];
        node()
        {
            cnt = 0;
            for(int i = 0; i < 26; i++) next[i] = NULL;
        }
    } trie;

    void Create_Trie(string str)
    {
        node* p = &trie;
        for(int i = 0; i < str.size(); i++) {
            int c = str[i] - 'a';
            if(p->next[c] == NULL)
                p->next[c] = new node;
            p = p->next[c];
            p->cnt++;
        }
    }

    int Search_Trie(string str)
    {
        node* p = &trie;
        for(int i = 0; i < str.size(); i++) {
            int c = str[i] - 'a';
            if(p->next[c] == NULL) return 0;
            p = p->next[c];
        }
        return p->cnt;
    }
}

int main()
{
    int n, q;
    cin >> n;
    string str;
    for(int i = 0; i < n; i++) {
        cin >> str;
        Create_Trie(str);
    }
    cin >> q;
    for(int i = 0; i < q; i++) {
        cin >> str;
        cout << Search_Trie(str) << endl;
    }
    return 0;
}