这是关于字典树的题。大致意思是：先创建了一个字典树，要求构造字串，创建一样的字典树。

本着还原做题思路的想法，进行此篇writeup。

IDA载入，弹出有关pdb信息的弹窗，发现pdb文件名被改成You want to leak information from pdb path? No way! QAQ。这是何意？难道是文件名称会泄露题名中的数据结构？

先看main函数，代码如下

流程明了，大概流程是：

再看主check流程：

主check流程包括三部分：

正如题目名所言，还得从数据结构入手。

再细分析主check流程时，发现了类。类名为诸如TrieTree此类。经查此为一种叫Trie树或字典数的数据结构。做下搬运工，相关的基本知识如下：

Trie树，又称字典树、前缀树、单词查找树、键树，是一种多叉树形结构，是一种哈希树的变种。Trie这个术语来自于retrieval，发音为/tri:/ “tree”，也有人读为/traɪ/ “try”。Trie树典型应用是用于快速检索（最长前缀匹配），统计，排序和保存大量的字符串，所以经常被搜索引擎系统用于文本词频统计，搜索提示等场景。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。
Trie树的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
 Trie树有3个基本性质：

答案还是要从比对的目标数据身上找。进行交叉引用查找。
发现目标数据的生成在sub_401900函数中，初始化过程中完成。伪代码如下：

原来此处相当于是手动生成字典树的数据结构，校验处是用类生成。结合检验处生成字典树的代码，推测字典树节点的数据结构如下：

set_count函数是设置单词计数的（检验时用到）。似乎这个单词计数对词频统计很有用啊。

到此，关于字典树中最重要的一部分数据结构出来了，那节点的check代码就好理解了。节点的check代码如下：

可以看出这是一个递归check，不仅check了节点的字符，还check了子节点数和单词计数。所以此题目的就是通过输入字串构造一个与预设字典树完全相同的字典树。

目标字典树的结构及其单词可以直接写出来，然后就是这些单词的符合异或cehck点的排列组合了。

下面是异或check算法，检查输入的4个子串的位置。

用于检验的目标字典树结构大致为:

输入的字符范围就在其中。而且输入字串为kx ctf ct9 c7Mk的组合或前半部分组合，而且通过字典树计数限制了子串出现与否及重复出现次数。
通过上面的计数，可以得到所有出现的单词：

kx c7 c7M(两次) c7Mk ct ct9 ctf

到这里就比较明晰了。

再加上异或确定的4组子串组合及顺序，这个排列组合可以就可以完全确定了。

输入分组情况如下：

第1组： 0/1
第2组： 2/3
第3组： 4/5/6
第4组： 7/8
第5组： 9/10/11/12
第6组： 13/14/15
第7组： 16/17/18
第8组： 19/20/21

异或检查输入的第1、4、6、7组子串。

如下为4个异或运算的可能取值。

综合上面条件，所以先出的4组为

子串中只有一个字串是4字节。所以9/10/11/12就为c7Mk。

由于计数除了c7M为2，其它都为1。所以剩下的3字节的两个位置就是此子串了。

还剩下一个2字节的子串。为了满足计数要求，没用过的只有ct了。
最后结果为:c7ctc7Mkxc7Mkctfct9c7M

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！