[week15] B - ZJM与生日礼物（选做）—— 字典树

题意

ZJM 收到了 Q老师 送来的生日礼物，但是被 Q老师 加密了。只有 ZJM 能够回答对 Q老师 的问题，Q老师 才会把密码告诉 ZJM。

Q老师 给了 ZJM 一些仅有 01 组成的二进制编码串, 他问 ZJM：是否存在一个串是另一个串的前缀.

Input

多组数据。每组数据中包含多个仅有01组成的字符串，以一个9作为该组数据结束的标志。

Output

对于第 k 组数据(从1开始标号)，如果不存在一个字符串使另一个的前缀，输出"Set k is immediately decodable"，否则输出"Set k is not immediately decodable"。
每组数据的输出单独一行

输入样例

01
10
0010
0000
9
01
10
010
0000
9

输出样例

Set 1 is immediately decodable
Set 2 is not immediately decodable

提示

分析

这也是一道用字典树解决的字符串问题。

• 字典树

1. 什么是字典树？字典树的作用？

字典树就是指的每个节点存储的都是一个字符的树。从根到任意一个叶子经过的路径就代表着一个完整字符串。

字典树主要用于判断一个字符是否是另一个字符的前缀。

2. 字典树类型

字典树类型：

• 节点
  每个节点有唯一的序号标记
• 根节点
• 孩子数组
  用一个二维数组记录每一个节点存在哪些孩子。
  child[n][m]：n代表节点序号，m代表孩子类型，存储的是孩子节点的序号。
• 结尾数组
  用一个数组标记每个字符串的结尾节点。
  flag[n]：n代表节点序号。若赋为true说明该节点是一个字符串的结尾。

3. 字典树构造

每一次插入都从根节点开始，依次插入字符串中的每一个字符：

• 判断当前节点i是否已经存在和当前待插入字符类型x相同的孩子
  • 若没有，则新建节点（最新序号tot + 1）存储该字符。在孩子数组中，将节点i对应字符类型x的数组空间赋值为该新节点序号tot + 1 ——> child[i][x] = tot + 1
  • 若已有，则判断该字符是否为当前字符串的结尾或是否为已存在字符串的结尾：
    • 若是当前字符串的结尾，则说明当前字符串一定被另一个已插入字符串包含；否则继续插入
    • 若是已存在（已插入树中）字符串的结尾，则说明当前正在插入的字符串一定包含一个完整的字符串；否则继续插入
• 当前字符插入后，将判断节点更新为新插入的节点，重复上述步骤
• 当字符串插入完成后，将最后一个判断节点标记为结尾节点

4. 字典树判断原理

根据前面的介绍我们已经知道，从根到任意叶子的路径都是一个完整的字符串。

但是可以想到，若字符串a包含字符串b，则字符串b无法从根走到任何一个叶子，而是属于a这条从根到叶子的路径中的一部分。

显然，判断两个字符串之间结尾节点的关系就是判断两个字符串包含关系的关键。

若仅存在两个字符串a和b，其中a已插入字典树中：

• 若当前b的某一个字符已经被标记为结尾节点，则代表a字符串从根开始沿相同路径到该字符处结束。显然b包含a。
• 若b的最后一个字符已经存在于字典树中，则代表b在完整走完a这条路径之前就提前结束。显然a包含b。

需要注意的是：

假设两个字符串a和b，长度分别为l1和l2（l1 >= l2）

若a和b前l3长度都完全相同，则显然它们插入在字典树的位置完全相同。
若第l3 + 1个字符不同，则a和b的第l3 + 1个字符将分别被插入在第l3个字符的不同孩子位置处。
就算剩下的所有字符都相同，a和b在第l3 + 1个之后的所有字符都将属于完全不同的路径。

这就是前面判断的基础。若一个节点已存在，则说明其一定属于于一个已存在的字符串中，只要该节点是一个结尾节点，不论其属于谁，都一定代表着存在包含关系。

• 题目分析

这就是一道典型的字典树问题。需要注意的是这个题目中涉及到的字符类型只有2种，即0和1。因此孩子数组中第二维只需要设置为2，即代表对每个节点来说会有0和1两个类型的孩子。

总结

1. 字符串还挺有意思😮

代码

//
//  main.cpp
//  lab2
//
//

#include <iostream>
#include <string.h>
#include <string>
using namespace std;

struct Tree         //字典树
{
    static const int N = 100000;        //最大节点数
    static const int charset = 2;       //字符种类
    int tot;            //最新节点序号
    int root;           //字典树根
    int child[N][2];        //第n个节点的孩子
    bool flag[N];            //标记第n个节点是否属于一个字符串的结尾
    
    Tree()          //构造函数
    {
        memset(child,-1,sizeof(child));
        root = 0;
        tot = 0;
    }
    
    void clear()        //清空
    {
        memset(child,-1,sizeof(child));
        root = 0;
        tot = 0;
    }
    
    bool insert(string s)     //插入字符串
    {
        int now = root;    //从根开始逐个插入每个字符
        bool judge = false;     //返回判断结果
        
        for( int i = 0 ; i < s.size() ; i++ )        //逐个插入字符串中的每个字符
        {
            int x = s[i] - '0';       //得到孩子序号
            
            if( child[now][x] == -1 )       //若当前节点不存在这个孩子
            {
                child[now][x] = ++tot;      //插入孩子，孩子所代表节点序号+1
                flag[now] = 0;              //标记该孩子节点不为结尾
            }
            else if( i == s.size() - 1 || flag[child[now][x]] )
                judge = true;
            //若当前节点已有该孩子，则判断该节点是否是结尾，若是则说明存在前缀
            
            now = child[now][x];        //从当前孩子节点向下继续添加
        }
        
        flag[now] = 1;      //标记最后一个节点为一个结束节点
        
        return judge;       //返回结果
    }
    
};


int main()
{
    ios::sync_with_stdio(false);
    
    int k = 0;
    string s;
    Tree t;
    bool judge = false;
    
    while( cin>>s )
    {
        if( s == "9" )
        {
            if( !judge )
                cout<<"Set "<<++k<<" is immediately decodable"<<endl;
            else
                cout<<"Set "<<++k<<" is not immediately decodable"<<endl;
            
            t.clear();
            
            judge = false;
            
        }
        else
        {
            if( t.insert(s) )       //只要有一个存在前缀则该组数据合法
                judge = true;
        }
    }
    
    return 0;
}