浅谈Trie树（字典树）

· · 题解

今天以一个例题为引子，传送门。

首先拿到这道题后，请自觉忽略题面，然后我们正经地分析一下题目：给出一个整数 n，接下来 n 行，每行给出一个字符串，组成一个集合，再给出一个整数 m，接下来 m 行，每行给出一个字符串并进行查询，如果给出的字符串在之前的集合中存在且此次查询为该字符串的第一次查询，则输出“OK”,如果给出的字符串在之前的集合中存在且此次查询不为该字符串的第一次查询（即在之前的操作中已经查询过），则输出“REPEAT”，但如果两个条件都未满足则输出“WEONG”。

再看这道题数据范围， n≤10000，m≤100000,而且给出的字符串都是长度小于等于50的小写字母串。看完之后第一反应————暴搜啊，是的吧，很多算法都是从暴搜开始，我也不能打破这个环节，那就码一码暴搜代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;//可以打万能头文件，但尽量在平时养成不用万能头文件的习惯 
int n,m;
bool emmm[10001];//判断是否被查询过 
string ss[10001],o;//ss数组存第一次给出的字符串，o表示每次要查询的字符串 
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>ss[i];
        //存完了 
    cin>>m;
    for(int j=1;j<=m;j++)
    {
        int op=0;//用于判断是否是因为查询为“OK”和“REPEAT”而退出 
        cin>>o;
    for(int i=0;i<n;i++)
    {
        if(emmm[i]==0&&ss[i]==o)
        {
            emmm[i]=1;
            op=1;
            cout<<"OK"<<endl;
            break;
        }
        else
        if(emmm[i]!=0&&ss[i]==o)
        {
            cout<<"REPEAT"<<endl;
            op=1;
            break;
        }
    }
    if(op==0)
    cout<<"WRONG"<<endl;
    //过程不再赘述 
    }
    return 0;
}

然后来看看提交结果! 不出所料，暴搜T了4个点，肿么办，开个O2试试 还是T了2个点，事实告诉我们，投机取巧不是好孩子，emmm，翻篇

既然暴搜大法不好使，我就再推一波玄学STL————map。这个在STL中可以看作是一个数组的优化，你们可以自己去了解一下，我现在先给一下代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<map>//map必开头文件 
using namespace std;
map<string,int>a;// 基本格式：map<数据类型 x，数据类型 y> 数组名 w ==>>w[x型数据]=y型数据 
string s;
int n,m;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        a[s]=1;//所读入的字符串所对应的数组打个标记 
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>s;
        if(a[s]==1)
        {
            cout<<"OK"<<endl;
            a[s]=-1;//所查询过的字符串所对应的数组打个标记
        }
        else 
        if(a[s]==-1)
        cout<<"REPEAT"<<endl;
        else 
        cout<<"WRONG"<<endl;
    }
    return 0;
}

对喽！！！完结撒花！！！

怎么可能，仔细看看代码就知道和今天要讲的只有半毛钱关系,这个做法主要是避免了每次查询的最坏结果都要跑一遍，所说的那半毛钱关系主要是要看下图，

红黄蓝分别表示样例的三次查询，第一次找到‘a’并标记，第二次找到‘a’但已被标记过，第三次找‘e’找不到，这样做出来的图就是一棵树，但是一旦数据过大，根节点就挂不了这么多儿子暗示你们这道题数据水，现在我们深入了解一下Trie树（字典树）。字典树顾名思义就是像字典一样去查找，也就是逐字符查找，一般有两种形式，接下来我以这个样例画一下图

这图丑的我怀疑人生

首先定义根节点深度为0

第一种做法是按读入顺序把每个字符各自编号，即第一次读入a时，a1为1号，而后b为2号，c1为3号，在读入到“acd”时，这个a2为4号，c2为5号，d1为6号，以此类推，这种做法就要为每一个字符留一个编号，数据大的话极容易爆。

第二种做法就是每个字符都只有一个编号，即第一次读入a时，a为1号，而后b为2号，c1为3号，在读入到“acd”时，这个a为1号，c2为3号，d1为4号，以此类推，这种做法就要为每一种字符留一个空间，相对前一种做法要小很多，所以我今天主讲第二种做法。

因为我们只是浅谈，所以还有任何深入知识可以和我私信讨论，在这只讲针对这道题的两个主要部分————插入与查找。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
int tot=0,em[1000001][26],bj[1000001];//tot是标号，em[i][j]=k表示编号为i的节点的第j个孩子是编号为k的节点，bj数组表示该字符串是否被查询过 
char c[1000001];//要用的字符串，改成字符数组，避免了拆分的麻烦（懒） 
inline void insert(){
    long long now=0,len=strlen(c+1);//习惯从1开始for循环，now表示编号 
    for(int i=1;i<=len;i++){
        long long sf=c[i]-'a';//题目中所用的是小写字母，所以-‘a’，而且只有小写字母，所以em数组的第2维只开了26，具体开多大根据题意 
        if(!em[now][sf])//如果那个位置没被存过 
        em[now][sf]=++tot;
        now=em[now][sf];//继续向下存 
    }
    bj[now]=1;//有的位置标成1 
}
inline int check(){
    long long now=0,len=strlen(c+1);//同上 
    for(int i=1;i<=len;i++){
        long long sf=c[i]-'a';
        if(!em[now][sf])//没被存过 
        return 2;
        now=em[now][sf];//继续往下找 
    }
    if(bj[now]==1)//没被查询过 
    {
    bj[now]=2;//标记为被查询过 
    return 0;
    }
    return 1;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",c+1);
        insert();
    }
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%s",c+1);
        int cx=check();
        if(cx==2)
        printf("WRONG");
        else
        if(cx==1)
        printf("REPEAT");
        else 
        printf("OK");
        printf("\n");//每一次输出要换行 
    }
    return 0;
}

真正的完结撒花，制图鸣谢大佬Zhouzerong