字典树（Trie 树）

1. 题目描述

给定 $n$ 个模式串 $s_1, s_2, \dots, s_n$ 和 $q$ 次询问，每次询问给定一个文本串 $t_i$，请回答 $s_1 \sim s_n$ 中有多少个字符串 $s_j$ 满足 $t_i$ 是 $s_j$ 的前缀。

一个字符串 $t$ 是 $s$ 的前缀当且仅当从 $s$ 的末尾删去若干个（可以为 0 个）连续的字符后与 $t$ 相同。

输入的字符串大小敏感。例如，字符串 Fusu 和字符串 fusu 不同。

2. 解析

对于每一个模式字符串，从第一个字符到最后一个字符建立一棵树，并给路径上的每一个标记点加上 $1$ 。输入检查字符串的时候，顺着树上的匹配路径往下走，一直走到不能再走，如果前面没有匹配的字符串了，说明答案就是 $0$ 。如果结束为止在树的某个节点上，答案就是这个点的标记数目。

3. 代码

#include <bits/stdc++.h>
using namespace std;
int q,n,m;
struct Node{
    vector <Node> children;
    char val;
    int cnt;
};
int main(){
    cin>>q;
    while(q--){
        cin>>n>>m;
        Node formatStr;
        for(int i=1;i<=n;i++){
            string s;
            cin>>s;
            // ptr to root
            Node *ptr=&formatStr;
            for(auto c:s){
                bool flag=1;
                for(auto &child:ptr->children){
                    if(child.val==c){
                        child.cnt++;
                        ptr=&child;
                        flag=0;
                        break;
                    }
                }
                if(flag){
                    // 说明没有现成的节点
                    Node newNode;
                    newNode.val=c;
                    newNode.cnt=1;
                    ptr->children.push_back(newNode);
                    ptr=&ptr->children.back();
                }
            }
        }
        for(int i=1;i<=m;i++){
            string s;
            cin>>s;
            Node *ptr=&formatStr;
            bool flag=1;
            int findCnt=0;
            for(auto c:s){
                for(auto &child:ptr->children){
                    if(child.val==c){
                        findCnt++;
                        ptr=&child;
                        flag=0;
                        break;
                    }
                }
                if(flag){
                    // 说明路走不通了。
                    break;
                }
            }
            if(findCnt==s.size()){
                cout<<ptr->cnt<<endl;
            }else{
                cout<<0<<endl;
            }
        }
    }
    return 0;
}

然而，这样的代码的运行速度不太理想，我们可以进一步优化。

考虑在查找子节点时降到 $log(n)$ 的复杂度，用 $set$ 存子节点，就能便捷地进行二分查找。

struct Node{
    set <Node> children;
    char val;
    int cnt;
    // 重定义小于号
    bool operator < (const Node &rhs) const{
        return val<rhs.val;
    }
};