很多CM都是基于各种算法的，很少有基于数据结构的CM。这个Trie树其实是学校考试的时候的一道题，然后那次考试我没考好（逃。。。考完之后我就去搜索了一下关于Trie树的资料，然后觉得这个挺有意思的，就根据这个数据结构写了个CM。。。

简单的说，Trie树是做了一个映射，将字符串映射到其对应的频率或者其它值。

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。——百度百科

比方说，现在有一些单词 kanxue ctf crack me crack，那么，crack会被映射到2，因为它出现过2次，而其它的会被映射到1。

——维基百科
如图所示，
trie树的性质：

根节点的字符串是空

其它节点字符串不为空

一个节点的所有子节点的所有字符串，不能有相同前缀：比方说abc和agf就不能在同一个节点下面，因为他们有相同前缀a

从根节点开始，走到任意一个节点，将走过的路径上的所有字符串拼接起来，那个终点节点的数便是拼接起来的字符串的映射到的频率（或者不一定是频率，也可以是某个其它value）。比方说，这张图，就很明显了。romane，就映射到1，ruber，就映射到5。

PS：我这道题实现的方法是，把前缀存在节点，每个节点可以存多个字符，所以查找子节点需要for遍历。根节点为空字符串，跟网上一般的实现有点区别（不然又成开源CM了）

这道题，正确答案是一个如图所示的Trie Tree:

首先判断输入长度和内容，全是字母数字和长度为22的检查，这个不说。

然后，会将输入拆成
xx xx xxx xx xxxx xxx xxx xxx
的形式，一个个地插入到一个空的Trie树中

然后如果这两个树相等，进入下一次检查

因为trie树只统计了频率，并没有统计顺序。这个时候就要判断一下，每个位置上是否是正确的值，为了防止直接的明文出现，这里使用了异或。

UML图如下

其中，带Abs的是抽象基类；Static是静态tree和node，也就是用来装正确答案的；而什么都没加的是用来放置输入的。

Node代表节点，而Tree的成员变量会存一个Node作为根节点

TrieTreeString和TrieTreeChildren分别用来代替STL的std::string和std::vector，目的是降低难度（这道题我出出来是想让大家能够做出来的）。
A类唯一作用就是在他的构造函数中初始化好正确答案的Trie，因为全局对象的构造函数会在main函数之前被调用。

其实很明显了，第一点是在pdb path中

\x00截断后，存在提示。当然这个可能发现的人不多。。。

这个应该就很明显了，没RTTI的类的类名都告诉你了。。。
(可恶的出题人因为觉得放这个提示会太简单，所以此条提示作废)

还有我在一个地方使用了dynamic_cast，所以说RTTI会被打开，那么其实类名已经告诉你了。。。

实际上，使用工具class_informer，完全可以获取到上面所说的类的继承关系的信息

（如何，在这个充满反调试与虚拟机保护的比赛中，是不是对这种提示感到了一丝温暖

https://github.com/igogo-x86/HexRaysPyTools

一个挺好用的IDA插件，逆C++的时候用这个特别爽，可以省去很多不必要的工作，而且特别适合解这道题，所以推荐给大家。安装说明在上面的repo中，这里不解释。。。

这里举个例子，比方说，我们想还原类TrieTreeNode。首先找到它的构造函数sub_403100，然后右键deep scan

这个的意思是，它会根据所有这个变量传达到的函数，根据访问偏移推测出其成员变量，这个工具原理就是这个，大家自行领会。。。

然后Edit->plugins->HexRaysPyTools

然后得出的结果会有collision，正常，因为对于同一个偏移可能有不同类型的访问方式，所以我们把一些无关的disable掉（选中按disable按钮），然后逆向发现偏移4处很可能是一个byte array，所以先双击_DWORD把类型改成_BYTE，再点array按钮。最后点finalize，创建结构体。如图所示。

与源代码对比一下

发现还是有点偏差，所以这个东西也不可能一键还原C++类，还是需要手工再逆向并且修改的。不过这个自动化识别已经可以帮我们省去很多工作了。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课