字符串的百草园
我家后面有一个很大的机房，相传叫作“字符串库”。现在是早已和教室一起租给隔壁的化竞班了，连那最末次的相见也已经隔了三四月，其中似乎确凿只有一些字符串；但那时却是我的乐园。
不必说朴素的模式匹配，野蛮的暴力枚举，高大的动态规划树；也不必说 KMP 在文本串里长吟，轻捷的 AC 自动机忽然从 Trie 树上直窜向云端里去了。单是周围的短短的 Trie 树一带，就有无限趣味。字符在这里低唱，指针在这里跳舞。翻开断砖来，有时会遇见哈希冲突；还有后缀数组，倘若用手指按住它的首项，便会“啪”的一声，从后面喷出一阵烟雾。字典树有伞盖般的结构，后缀树有臃肿的结点。有人说，Trie 的根是有像人形的，理解了便可以成仙，我于是常常研究它，连续不断地调试，也曾因此弄坏了键盘，却从来没有见过有一个结构像人样。如果不怕 WA，还可以摘到后缀自动机，像小珊瑚珠攒成的小球，又酸又涩，色味都比线段树要好得远。
长的教练是不常来的，因为相传这园里有一条很大的“红黑树”。
长的教练曾经讲给我一个故事听：先前，有一个 OIer 在机房里刷题，夜晚在屏幕前写代码时，突然听到有人叫他。答应着，四面看时，却见一个美女的脸露在屏幕前，向他一笑，隐去了。他很高兴；但竟给那走来夜谈的教练看出了破绽，说他脸上有些妖气，一定遇见“美女蛇”了；这是人首蛇身的怪物，能唤人名，倘一答应，夜间便要来吃这人的肉的。他自然吓得要死，而那教练却道无妨，给他一个小盒子，说只要放在枕边，便可高枕而卧。他虽然照样办，却总是睡不着——当然睡不着的。到半夜，果然来了，沙沙沙！门外像是风雨声。他正抖作一团时，却听得豁的一声，一道金光从枕边飞出，外面便什么声音也没有了，那金光也就飞回来，敛在盒子里。后来呢？后来，教练说，这是飞蜈蚣，它能吸蛇的脑髓，美女蛇就被它治死了。
结末的教训是：所以倘有陌生的变量名出现在代码里，你万不可轻易使用它。
这故事很使我觉得做 OIer 之险，夏夜乘凉，往往有些担心，不敢去看代码，而且极想得到一盒教练的飞蜈蚣。走到 Trie 树的旁边时，也常常这样想。但直到现在，总还没有得到，但也没有遇见过红黑树和美女蛇。叫我变量名的陌生函数自然是常有的，然而都不是美女蛇。
冬天的 Trie 树比较的无味；雪一下，可就两样了。拍雪人（将自己的全形印在雪上）和塑雪罗汉需要人们鉴赏，这是荒园，人迹罕至，所以不相宜，只好来“对拍”。薄薄的雪，是不行的；总须积雪盖了地面一两天，数据点久已无处生成的时候才好。打开一块磁盘，露出接口，用一台旧电脑支起一面大的编译器，下面放些测试数据，电脑上连着一条长线，人远远地操作着，看数据点进去运行，走到编译器里面的时候，将脚本一跑，便出结果了。但所得的是小数据居多，也有大数据“TLE”，性子很躁，跑不过夜的。
这是学长所传授的方法，我却不大能用。明明见它们进去了，运行了，跑去看，却什么都没有，费了半天力，对出来的不过三四组。学长是小半天便能对出几十组，装在 U 盘里叫着撞着的。我曾经问他得失的缘由，他只静静地笑道：你太性急，来不及等它走到中间去。
我不知道为什么家里的人要将我送进书塾里去了，而且还是全城中最严的书塾。也许是因为把Trie树里的字符都玩坏了吧，也许是因为将指针乱丢进内存池里去了吧，也许是因为站在树上看代码看得太久了吧……都无从知道。总而言之：我将不能常到 Trie 树了。Ade，我的哈希冲突！Ade，我的 KMP 和 AC 自动机们！
出门向东，不上半里，走过一道石桥，便是我的先生的家了。从一扇黑油的竹门进去，第三间是书房。中间挂着一块匾道：三味书屋；匾下面是一幅画，画着一只很肥大的梅花鹿伏在古树下。没有孔子牌位，我们便对着那匾和鹿行礼。第一次算是拜孔子，第二次算是拜先生。
第二次行礼时，先生便和蔼地在一旁答礼。他是一个高而瘦的老人，须发都花白了，还戴着大眼镜。我对他很恭敬，因为我早听到，他是本城中最博学的人，尤其精通字符串。
我便对着书屋里的梅花鹿行礼，算是拜了师。先生给我上了第一课，便是在黑板上写下两个大字：“后缀”。
“后缀！”他说。
于是大家放开喉咙读一阵书，真是人声鼎沸。有念“parent 树父亲是后缀”的，有念“endpos 集合要合并”的，有念“状态转移要复制”的，有念“link 指针往上跳”的……先生自己也念。后来，我们的声音便低下去，静下去了，只有他还大声朗读着：
“状态数不超过
2n ，转移数不超过3n ，构建时间复杂度O(n) ……”我疑心这是极好的文章，因为读到这里，他总是微笑起来，而且将头仰起，摇着，向后面拗过去，拗过去。
先生读书入神的时候，于我们是很相宜的。有几个用纸糊的键盘敲代码的，也有用指甲在桌上模拟算法的。我是喜欢在纸上画状态转移图的，用一种叫作“自动机”的图画。读的书多起来，画的图也多起来；代码没有写，图的成绩却不少了，从最简单的 DFA 到 NFA，终于到 SAM。
三味书屋后面也有一个小机房，虽然小，但在那里也可以偷偷打游戏，或是在草稿纸上寻思路。最好的工作是捉了 bug 喂样例，静悄悄地没有声音。然而同窗们到机房里的太多，太久，可就不行了，先生在书房里便大叫起来：
“人都到哪里去了！”
人们便一个个陆续走回去；一同回去，也不行的。他有一条戒尺，但是不常用，也有罚站的规矩，但也不常用，普通总不过瞪几眼，大声道：
“读书！”
于是大家放开喉咙读一阵书，真是人声鼎沸。有念“广义后缀自动机”的，有念“子串出现次数”的，有念“本质不同子串数”的……先生自己也读书。后来，我们的声音便低下去，静下去了，只有他还大声朗读着：
“当
maxlen[q] > maxlen[p] + 1时，需要复制节点……”我疑心这是极难的文章，因为读到这里，他总是紧皱眉头，而且将头埋下，叹着，向前面垂下去，垂下去。
大家便接着哄笑起来：书屋里充满了快活的空气。
先生对于我，渐渐的也不那么严厉了。他让我自己看博客，看论文，从《后缀自动机——张一飞的训练营》到《后缀自动机学习笔记——陈立杰》。我于是常常去图书馆，在那些晦涩的符号中寻找一点乐趣。也终于明白，原来这“后缀自动机”真是极难的东西，至今也没有几个人能完全弄懂。
后来，因为要准备竞赛，我对 SAM 的兴致也终于完全消散。但直到现在，我还是不知道那 SAM 究竟是怎样构建的——也许先生也不知道罢。
如今，我已经离开书屋很久了，但每当看到字符串的题目，总会想起那摇头晃脑的先生，和那快活的空气。
Ade，我的 Trie 树！Ade，我的后缀自动机和书屋！
以上内容由 Deekseep 生成。