引入

给定一个s，让你查找字符串数组a中有没有s

一般大家都会想到暴力查找，对吧，但如果出题人非常凉心的话…那一片TLE和MLE可以说是非常蔚为壮观

那假如让你用这个暴力方法查字典…那么你肯定瞬间炸裂，对吧。

所以，你找单词的时候，都是先找首字母，然后找第二个字母，然后逐渐找到你要找的那个单词吧。

而字典树也是通过模拟这一过程来实现更高效的查询

一旦明白了这点，字典树你应该也差不多能敲出来了

代码

其实字典树和哈希有些相似之处，他们都通过给字符串编号来实现更高效的查找

int cnt[100005],f[100005][31],n,idx;
//cnt记录字符串的数量，f为字典树，idx为字符串标号 
void insert(string s) //插入字符串s 
{
    int p=0; 
    for(int i=0;i<s.size();i++)
    {
        int tem=s[i]-'a'+1;
        if(!f[p][tem]) f[p][tem]=++idx;//如果字典中查不到这个字符串，则给这个字符串一个新的编号 
        p=f[p][tem];//往下查找 
    }
    cnt[p]++;//计算该字符串数量 
}
void Found(string s)//查询字符串s的数量 
{
    int p=0;
    for(int i=0;i<s.size();i++)
    {
        int tem=s[i]-'a'+1;
        if(f[p][tem]) p=f[p][tem];//向下查询 
        else//一旦有一个字母查不到了，则没有这个字符串 
        {
            cout<<0<<endl;
            return;
        }
    }
    cout<<cnt[p]<<endl;//查到了s的编号 
    return;
}

一道例题讲解

题面

给定 n 个模式串 s(1),s(2)…s(n) 和 q 次询问，每次询问给定一个文本串t(i)，请回答 s(1),s(2)…s(n)中有多少个字符串 s(j) 满足 t(i) 是 s(j) 的前缀。

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

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

对于全部的测试点，保证 1≤T,n,q≤1e5，且输入字符串的总长度不超过3×1e6。输入的字符串只含大小写字母和数字，且不含空串。

思路

将所有字符串的前缀加入到字典树中，查询时可以直接查询

代码

#include<bits/stdc++.h>
using namespace std;
int cnt[100005],f[100005][155],n,idx,m;
void insert(string s)
{
    int p=0;
    for(int i=0;i<s.size();i++)
    {
        int tem=int(s[i]);
        if(!f[p][tem]) f[p][tem]=++idx;
        p=f[p][tem];
    }
    cnt[p]++;
}
void Found(string s)
{
    int p=0;
    for(int i=0;i<s.size();i++)
    {
        int tem=int(s[i]);
        if(f[p][tem]) p=f[p][tem];
        else
        {
            cout<<0<<endl;
            return ;
        }
    }
    cout<<cnt[p]<<endl;
    return;
}
int t;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        memset(f,0,sizeof(f));
        memset(cnt,0,sizeof(cnt));
        idx=0;
        for(int i=1;i<=n;i++)
        {
            string s,t="";
            cin>>s;
            for(int j=0;j<s.size();j++)//将所有字符串的前缀加入到字典树
            {
                t+=s[j];
                insert(t);
                //cout<<t<<endl;
            }

        }
        for(int i=1;i<=m;i++)
        {
            string s;
            cin>>s;
            Found(s);
        }
    }
    return 0;
}