后缀树的实现形式

————《高级数据结构》
上述后缀树T是根据字符串S的所有后缀构建的。有时候这个S可以是要给字符串集合，所以后缀树T是根据所欲字符串的后缀构建的。这种后缀树也叫做广义后缀树。
一种很自然的构建方式可以给每个字符串加两两不同的结尾符，这些结尾符没有在任何字符串中出现过。然后，我们将这些添加了结尾符的字符串首尾相接作为一个整体来构建其后缀树。由于任何一个后缀都不是其他后缀的前缀，并且任意连个字符串的结尾符不同，所以我们还是可以方便地找到所需要的后缀。不过，这种实现方式会多了许多没有意义的后缀，在空间和代码优美程度上都差强人意。
另外一种实现方式，是将每个字符串加相同的结尾符后依次添加进书中。在第i+1次添加字符串Si+1时，我们像在单独构建后缀树时一样，在原来树基础上逐步构建Si+1的隐式树。因为这种构建过程不会影响前i次的后缀，并且仍可以保证Si+1的所有后缀都被添加进来。这种方式会导致一个后缀属于多个字符串。所以在叶节点上，我们还需要开一个列表来终止于此的那些字符串编号。
6.代码实现
在实现代码之前，我们需要对后缀树的存储方式做一个讨论。主要原因是后缀树中涉及的字符种类范围不确定，可以是26个英文字母，可以是所有汉字，或者更糟糕。一下是常用的几种存储方式。
（1)数组。用数组存储孩子节点是最常用的方法之一。如果我们事先知道字符串中出现的字符集的大小，假设为C，那么后缀树中每个节点都需要维护一个包含C个元素的数组。这种方式可以在O(1）的时间内执行查找，插入操作，其主要缺点有空间浪费以及需要字符集固定。
（2）链表。用链表来维护孩子节点是，每个节点需要存储自己的第一个孩子节点，同时每个节点还要维护自己的相邻兄弟节点，这样就可以遍历一个节点的孩子了，不过这样查询和插入都需要O（C）的时间来定位了。一个小优化是可以将孩子系欸但维护为有序的，这样维护成本不会增加，但是会降低期望查找时间。这种以时间换空间的方式使得后缀树支持可变字符集，并且将空间节省到最小。
（3）.平衡树。用平衡树来存储孩子节点可以算是对链表存储的一种改进。这样可以将每次查询，插入操作的时间复杂度降到O（log2C）。不过鉴于平衡树结合后缀树的编码复杂度，这种方法仅当C较大的时候比较合适。
（4）哈希表。不论是用开散列还是闭散列的方式，这种存储方式仍然需要找到一个时间和空间的平衡点，并且线性时间复杂度对哈希函数的要求也比较高。
综上所述，不同的表示方式有各自的优点和缺点，没有绝对优秀的方法。所以，具体的实方式还是要依据具体问题来定。有些时候甚至可以将几种表示方式联合起来在一个后缀树中使用。
以下的代码将用链表存储结构存储，并且我们直接构建广义后缀树，单个字符串的后缀树可以看作广义后缀树的特例。