Trie树

字典树,又称前缀树,是用于快速处理字符串的问题,能做到快速查找到一些字符串上的信息。
另外,Trie树在实现高效的同时,会损耗更多的空间,所以Trie是一种以空间换时间的算法。

Trie树的思想

我也不明白怎么表达,我们看图吧!

Kur1su 
the
great
god

图片说明
理解了吗?没理解我再想想办法。
我们用字典树干嘛?是不是更快的查询?那么在上面的trie树上是如何体现的呢?比如说我要查"great",那么我的查询过程就是图片说明 。从树上可以知道"great"和"god"的公共前缀是'g'。
从树上可以看出,想要插入一个字符串,就顺藤摸瓜一波,如果摸到一半,藤断了,那么我们就另起门户,按照字符串中的顺序新建一些节点连接在之前藤的末尾就好。如果你插入完了整个字符串,结果藤还没断,那么我们就给这个节点打个标记,表明这里是某个字符串的结尾。
这样的话,对于每次插入复杂度就是o(len(s))。
上面是插入的过程,那么你再想想查询呢?是不是一个道理!也是一直向下摸,不同点在于,如果你的藤没断,但是这个位置的没有打标记,这样,即使你在这个树上找到了字符串,但也是没找到的,只能说有一个字符串的前缀是它。对于每次查询复杂度就是o(len(s))。

Trie的实现

看了这么久,你也应该能想到node要怎么写了吧。

节点

struct node
{
    int son[26];//我们这里只考虑小写字母,要是想要把全部字符都放进去,你这开大点就好。
    bool f;//这个就是我们终点标记。
} trie[maxn];

插入操作

void insert(string s)
{
    int now=0;//根节点为0
    int len=s.length();//需要插入的串的长度
    for(int i=0;i<len;i++)
    {
        if( trie[now].son[s[i]-'a'] )//如果在之前插入过了部分前缀一样的字符串,就不用创建新的点了,也就是顺藤摸瓜的过程
        {
            now=trie[now].son[s[i]-'a'];
        }
        else//藤断了,就要自己创建新的节点。
        {
            trie[now].son[s[i]-'a']=num++;
            now=trie[now].son[s[i]-'a'];
        }
    }
    trie[now].f=1;//终点标记的修改
}

查询操作

void find(string s)//返回值类型视具体情况
{
    int now=0;
    int len=s.length();
    int now=0;
    for(int i=0;i<len;i++)
    {
        if( trie[now].son[s[i]-'a'] )
        {
            now=trie[now].son[ s[i]-'a'];
        }
        else
        {
            cout<<"查询失败"<<endl;
            return ;
        }
    }
    if( trie[now].f)
    {
        cout<<"查询成功"<<endl;
        return ;
    }
    else
    {
        cout<<"查询失败"<<endl;
        return ;
    }
}

这么一来字典树的基本操作你就学会了!
来用我练习的题来检测自己吧!

练习题

P2580 于是他错误的点名开始了

phone list

Immediate Decodability

The XOR Largest Pair

秘密消息Secret Message

Nikitosh 和异或

练习题解答

P2580 于是他错误的点名开始了
思路:就是查询每个串是否存在,若存在再看是不是第一次被查询。

//team yglance+xhwl+TTD
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=3e6+7;//这个值大概是node的son数组大小与题目规模的乘积,往大了开就好。
const double pi=acos(-1);
using namespace std;
int t,n,m;
int num=1;//这里也可以写成0,下面insert 的时候改成++num就好
struct node 
{
    int son[26];//全是小写字母的字符串,数组大小开26,27也可以 
    bool f;//表示这里是不是某个字符串的最后一个字符 
    int cnt;//这是为了本题而增加的一个标志,表示这个字符串是否有被查询过。 
} trie [maxn]; 
void insert(string s)
{
    int len = s.length();
    int now=0;
    for(int i=0;i<len;i++)
    {
        if(trie[now].son[s[i]-'a'])
        {
            now=trie[now].son[s[i]-'a'];
        }
        else
        {
            trie[now].son[s[i]-'a']=num++;
            now=trie[now].son[s[i]-'a'];
        }
    }
    //别忘记打上终点标记
    trie[now].f = 1;
    return ;
} 
void find(string s)
{
    int len    = s.length();
    int now    = 0;
    for(int i=0;i<len;i++)
    {
        if(trie[now].son[s[i]-'a'])
        {
            now=trie[now].son[s[i]-'a'];
        }
        else
        {
            cout<<"WRONG"<<endl;
            return ;
        }
    } 
    if(! trie[now].f )
    {
        cout<<"WRONG"<<endl;
        return ; 
    }
    else
    {
        if(! trie[now].cnt)
        {
            cout<<"OK"<<endl;
            trie[now].cnt++;
            return ;
        }
        else
        {
            cout<<"REPEAT"<<endl;

            return ;
        }
    }
 } 
int main()
{
    ios::sync_with_stdio(false);
       cin>>n;
       string s;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        insert(s);
    }
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        find(s);
    } 
     return 0;
}

phone list
思路:跟上面一样,可以先把所有的串放进VECTOR,然后执行插入操作,最后再对每个串进行查询操作,查询到前缀串,就输出NO,否则YES。

//team yglance+xhwl+TTD
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=2e6+7;
const double pi=acos(-1);
using namespace std;
struct node
{
    int son [10];
    int f;
} trie[maxn];
int num=0;//这次用的是0,所以下面是++num
void insert(string s)
{
    int len=s.length();
    int now=0;
    for(int i=0;i<len;i++)
    {
        if(trie[now].son[s[i]-'0'] !=0 )
        {
            now=trie[now].son[s[i]-'0'];
        }
        else
        {
            trie[now].son[s[i]-'0']=++num;
            now=trie[now].son[s[i]-'0'];
        }
    }
    trie[now].f=1;
}
int x=1;//这个就是有无前缀的标志,1代表的是没有,也就是需要输出yes的情况
void find(string s)
{
    int len=s.length();
    int now=0;
    for(int i=0;i<len;i++)
    {
        if(trie[now].son[s[i]-'0'] !=0 )
        {
            now=trie[now].son[s[i]-'0'];
            if(trie[now].f==1&&i!=len-1) //存在前缀字符串,并且不是自己本身
            {
                x=0;
                return;
            }
        }
    }

    return ;
}
vector<string > vec;
string s;

int main()
{
    ios::sync_with_stdio(false);
    //freopen("in.in","r",stdin);
    //freopen("mine.out","w",stdout);
    int t;
    cin>>t;
    while(t--)
    {
        x=1;
        num=0;
        vec.clear();
        memset(trie,0,sizeof(trie));
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>s;
            vec.push_back(s);
            insert(s);
        }
        for(size_t i=0;i<n;i++)
        {
            find(vec[i]);
            if(x==0)
            {
                cout<<"NO"<<endl;
                break;
            }
        }
        if(x)
        {
            cout<<"YES"<<endl;
        }
    }
     return 0;
}

Immediate Decodability
思路:也是一样的找前缀。不同点在于输入,当输入'9'的时候表示输入结束。进行操作就好。
其实这题我觉得挺烦的,弄得我直接自闭。

//team yglance+xhwl+TTD
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
int num=0;
struct node 
{
    int son[2];//01串,数组长度设置为2 就好 
    int f;
}trie[maxn];
string s[maxn];
void insert(string s)//插入操作没有任何改变 
{
    int len=s.length();
    int now=0;
    for(int i=0;i<len;i++)
    {
        if(trie[now].son[s[i]-'0'])
        {
            now=trie[now].son[s[i]-'0'];
        }
        else
        {
            trie[now].son[s[i]-'0']=++num;
            now=trie[now].son[s[i]-'0'];
        }
    } 
    trie[now].f=1;
}
int find(string s)
{
    int len=s.length();
    int now=0;
    for(int i=0;i<len;i++)
    {
        if(trie[now].son[s[i]-'0'])
        {
            now=trie[now].son[s[i]-'0'];
        }
        else
        {
            return 0;
        }
    } 
    //这个串已经被遍历完了,如果这时候的son还存在,那么就有一个别的串以它为前缀 
    if(trie[now].son[0]||trie[now].son[1])
    {
        return 1;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    int n=0;
    int bianhao=1;
    int f=0;
    while(cin>>s[n])
    {
        if(s[n]=="9")//解决问题 
        {
            for(int i=0;i<n;i++)
            {
                f=find(s[i]);
                if(f)//注意就是不一定需要全部查询的 
                {
                    break;
                }
            }
            if(f)
            {
                printf("Set %d is not immediately decodable\n",bianhao++);
            }
            else
            {
                printf("Set %d is immediately decodable\n",bianhao++);
            }
            //记得重置,因为不重置,我WA了一下午。 
            n=0;
            num=0;
            f=0;
            memset(trie,0,sizeof(trie));
        }
        else 
            insert(s[n++]);
    }
     return 0;
}

The XOR Largest Pair
思路:首先你肯定是知道异或的计算的,就是二进制表示下,对于同一位,如果两个数不同,则该位置的异或值为1。相同为0。那么对于这个题,我们把每个数的二进制表示都放进去,然后去查询有没有不一样的不就行了。注意的是我们要从高位开始,并且如果没有不一样的,也不能退出,而要继续找下去。

//team yglance+xhwl+TTD
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=4e6+7;
const double pi=acos(-1);
using namespace std;
int num=1;
struct node
{
    int son[2];//二进制数,数组开2就好
    ll f;
}trie[maxn]; 
string fenjie(ll n)//分解为2进制数
{
    string s="";
    for(int i=0;i<32;i++)
    {
        s+=char((n&1)+48);
        n>>=1;
    }
        //注意这个s可不是n的二进制表示。顺序反了
    string ss="";
    for(int i=31;i>=0;i--)
    {
        ss+=s[i];
    }
    return ss;
}
void insert(string s)//插入还是没变化
{
    int len=32;
    int now=0;
    for(int i=0;i<len;i++)
    {
        if(trie[now].son[s[i]-'0'])
        {
            now=trie[now].son[s[i]-'0'];
        }
        else
        {
            trie[now].son[s[i]-'0']=num++;
            now=trie[now].son[s[i]-'0'];
        }
    }
    trie[now].f=1;
}
ll find(string s)
{
    ll mx=0;//本次
    int a[32];//这个就是两个数异或后得到的答案数字的二进制表示形式
    int len=32;
    int now=0;
    for(int i=0;i<len;i++)
    {
        if(trie[now].son[!(s[i]-'0')])//要取反哦 
        {
            now=trie[now].son[!(s[i]-'0')];
            a[31-i]=1; //i越小,对应位置的值是越大的!
        }
        else
        {
            now=trie[now].son[s[i]-'0'];
            a[31-i]=0;
        }
    }
    ll q=1;
    for(int i=0;i<len;i++)
    {
        mx+=q*a[i];
        q<<=1;
    }
    return mx;
}
int main()
{
    ios::sync_with_stdio(false);
    //freopen("in.in","r",stdin);
    //freopen("mine.out","w",stdout);
       int n;
       cin>>n;
       ll a;
       string s;
       ll mx=0;
       for(int i=0;i<n;i++)
       {
           cin>>a;
           s=fenjie(a);
           insert(s);
           mx=max(mx,find(s));

           //cout<<a<<"  "<<s<<endl;
    }
    cout<<mx<<endl;
     return 0;
}

秘密消息Secret Message
思路:容易知道,需要输出的为:密码是多少条信息的前缀。那么这么一来又变成了模板了。这题的关键点就是信息长度和密码长度都未知的,他只搞到了部分,所以可以快乐YY,增加答案大小。

//team yglance+xhwl+TTD
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e6+7;
const double pi=acos(-1);
using namespace std;
int num=1;
struct node 
{
    int son[2];//二进制 
    int f;
    int cnt;
}trie[maxn];
void insert(string s,int len)//因为题目给了你长度,多添加一个长度参数 
{
    int now=0;
    for(int i=0;i<len;i++)
    {
        if(trie[now].son[s[i]-'0'])
        {
            now=trie[now].son[s[i]-'0'];
        }
        else
        {
            trie[now].son[s[i]-'0']=num++;
            now=trie[now].son[s[i]-'0'];
        }
        if(i!=len-1)//值得注意的是这里! 
            trie[now].cnt++;//有信息经过了这里 
    }
    trie[now].f++;//以这里为终点的信息 数量增加 
}
int find(string s,int len)
{
    int now=0;
    int ans=0;
    for(int i=0;i<len;i++)
    {
        if(trie[now].son[s[i]-'0'])
        {
            now=trie[now].son[s[i]-'0'];
        }
        else//后面已经没有匹配的了,退出就好。
        {
            return ans;
        }
        if(trie[now].f) //存在以这里为终点的信息 ,这些信息后缀是不知道的。所以可以让他们成为答案中的一员。 
        {
            ans+=trie[now].f;
        }
    }
    return ans+trie[now].cnt;//最后再加上经过这里的信息就好。 
}
int main()
{
    ios::sync_with_stdio(false);
    //freopen("in.in","r",stdin);
    //freopen("mine.out","w",stdout);
    int n,m;
    cin>>m>>n;
    int q;
    string s="";
    char c;
    //int mx=0;
    for(int i=0;i<m;i++)
    {
        cin>>q;
        s="";
        for(int j=0;j<q;j++)
        {
            cin>>c;
            s+=c;
        }
        insert(s,q);
    }
    for(int i=0;i<n;i++)
    {

        cin>>q;
        s="";
        for(int j=0;j<q;j++)
        {
            cin>>c;
            s+=c;
        }
        cout<<find(s,q)<<endl;
    }
    //cout<<mx<<endl;
     return 0;
}

还剩几个题,以为自己会了,结果发现自己好像解释不清楚。真是离谱,等我去琢磨一下。
写在最后:
本文是参考该文章 写的(因为我是看这该文学的,讲的很好,如果看完我的辣鸡文章你依然不能完全理解的话,可以去看看)
太菜了~现在看什么都是字典树。结果就是我2020JSCPC的H题T了无数发。从dp到爆搜。