字典树（Trie树，单词查找树）

基本要点

根节点不包含字符，除根节点外每一个节点都只包含一个字符；
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
每个节点的所有子节点包含的字符都不相同。

基本操作

查找、插入、删除

实现过程

从根节点开始搜索（先记住开头）；
将单词的每个字母一一进行取出并进行操作（各种操作）；

简易模板(插入及询问某字符串数量)

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

struct P{ //节点定义
    int son[26];
    int cnt;
    P() {
        memset(son,0,sizeof(son));
        cnt=0;
    }
};

int n;
int tmp; //节点数，记得在主函数里置零
vector<P> trie;

void add(string l) {
    int len=l.size();
    int now=0;
    for(int i=0; i<len; ++i) {
        if(!trie[now].son[l[i]-'a']) {
            trie[now].son[l[i]-'a']=++tmp;
            now=tmp;
            trie.push_back(P());
        }
        else now=trie[now].son[l[i]-'a'];
        if(i==len-1) trie[now].cnt++; //若求前缀相同的数量，则不需要i==len-1就需要加上去。
    }
}

int find(string l) {
    int len=l.size();
    int now=0;
    for(int i=0; i<len; ++i) {
        if(!trie[now].son[l[i]-'a']) return 0;
        now=trie[now].son[l[i]-'a'];
        if(i==len-1) return trie[now].cnt;
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    tmp=0, trie.push_back(P()); //初始化
    cin>>n;
    for(int i=0; i<n; ++i) {
        string l;
        cin>>l;
        add(l);
    }
    int q;
    cin>>q;
    while(q--) {
        int query;
        string l;
        cin>>query>>l;
        if(query==1) add(l);
        else cout<<find(l)<<endl;
    }
}

实例分析

Phone List（HDOJ 1671）

Problem Description
Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:

Emergency 911
Alice 97 625 999
Bob 91 12 54 26

In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.

Input
The first line of input gives a single integer, 1 <= t <= 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 <= n <= 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output
For each test case, output “YES” if the list is consistent, or “NO” otherwise.

Sample Input
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

Sample Output
NO
YES

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<cstdlib>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<cctype>
using namespace std;

struct P{
    int son[10];
    bool stop;
    P() {
        memset(son,0,sizeof(son));
        stop=0;
    } //简洁初始化
}; //定义节点

int n, f;
int tmp;
vector<P> trie; //由于不知具体节点个数，使用vector节约空间

void add(string l) {
    int len=l.size();
    int now=0; //一定从头开始
    for(int i=0; i<len; ++i) {
        if(!trie[now].son[l[i]-'0']&&trie[now].stop) {
            f=1;
            break;
        } //前面有电话是此电话的前缀
        else if(trie[now].son[l[i]-'0']) {
            if(i==len-1) {
                f=1;
                break;
            } //此电话是前面某电话的前缀
            now=trie[now].son[l[i]-'0'];
        }
        else if(!trie[now].son[l[i]-'0']) {
            trie[now].son[l[i]-'0']=++tmp;
            now=tmp;
            trie.push_back(P());
            if(i==len-1) trie[now].stop=1; //表示一个完整电话
        }
    }
    return;
}
int main() {
    int t;
    string l;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        tmp=f=0;
        trie.clear(); //清空Trie树
        trie.push_back(P()); //把根节点放进去
        for(int i=0; i<n; ++i) {
            cin>>l;
            if(!f) add(l); //如果前面已经判断成NO了，就没必要继续啦。
        }
        if(f) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}