后缀树

后缀树入门感性认识后缀树一棵后缀树包含了一个或者多个字符串的所有后缀。空字符串也算其中一个后缀。对于字符串banana，其所有后缀为：bananaananananaananaa空。通常为了更清楚地表示出后缀，我们在字符串末尾添加一个特殊字符作为结束标记，在这里我们使用$。因此banana的所有后缀就可以表示为：banana$anana$nana$ana$na$a$$感性认识后缀树banana所对应的后缀树如下：Trie为了更好地理解后缀树，我们先来看一种被称为Trie的数据结构。下图是一个典型的Trie：Trie的定义Trie是一种搜索树，可用于存储并查找字符串。Trie的每一条边都对应一个字符。在Trie中查找字符串S时，只需依次枚举S的每个字符，同时从Trie的根节点开始选择相应的边往下走。如果枚举完的同时到达Trie的叶子节点，说明S存在于Trie中。如果未到达叶子节点或者枚举中途发现没有任何对应的边，说明S没有被包含在Trie中。在Trie中查找字符串查找TOSS的过程如下：压缩后的Trie我们可以对Trie进行压缩，对只有一个儿子的节点进行合并：后缀树与Trie事实上，后缀树就是一个压缩后的Trie，存储了字符串所有的后缀。后缀树的应用1查找一个字符串S是否包含了字串T如果S包含T，那么T必定是S的某个后缀的前缀。因为S的后缀树包含了所有的后缀，因此只需对S的后缀树使用和Trie相同的查找方法即可。后缀树的应用1举例：在banana中查找an后缀树的应用2统计S中出现T的次数每出现一次T，必定对应着一个不同的后缀，而这所有的后缀又都有着共同的前缀T。因此这些后缀在S的后缀树中必定属于某一棵子树。这棵子树的叶子数便等于T在S中出现的次数。后缀树的应用2举例：统计banana中出现an的次数后缀树的应用3找出S中最长的重复子串。所谓重复子串是指出现了两次以上的子串。首先定义节点的“字符深度”=从后缀树根节点到每个节点所经过的字符串总长。找出有最大字符深度的非叶节点，则从根节点到该非叶节点所经过的字符串即为所求。后缀树的应用3举例：banana的最长重复子串为ana后缀树的存储为了节省不必要的空间浪费，我们不在边上存储字符串，而是存储该字符串在原串中的起止位置。空间复杂度O(n)后缀树的构造最简单的方法：使用类似于Trie的构造方法。此时算法复杂度为O(n^2)后缀树的构造后缀树可以用O(n)的算法构造出来，但是它们都十分复杂。我们这里介绍其中一种比较常见的。后缀树的构造基本思路：先往树中插入最长的后缀，即字符串本身。然后插入次长的后缀，再然后插入第三长的后缀，如此反复一直到空后缀被插入为止。这个过程也可以这样描述：1、插入S本身2、若上一个插入的后缀为S，令S=aw（这里a表示S的第一个字符，w表示S去掉a以后所得到的后缀）。往树中插入w。重复本操作直到S=$。后缀树的构造每次插入一个后缀，会产生一个新的叶节点，同时可能产生一个新的非叶节点。如下图，可能出现的是(a)-(b)(b)-(c)两种情况，但不可能出现(b)-(d)这种情况。后缀树的构造定义后缀连接（SuffixLink）=从节点A指向节点B的指针，B所表示的子串是A所表示的子串的最长后缀，即根节点到A所经过的字符串为S=aw，到B所经过的字符串为w。后缀树的构造该算法的关键在于在插入后缀的过程中，利用非叶节点的后缀连接实现快速插入，同时维护新插入的非叶节点的后缀连接。在插入的过程中，需要用到后缀树的子串快速定位。如果已知某个子串存在于后缀树中，那么我们可以对它进行快速定位。其思想是只匹配当前可选择的边的第一个字符。后缀树的构造举例：快速定位anan后缀树的构造算法所用符号描述S=需要构造后缀树的字符串Si=从第i个字符开始的后缀N(Si)=Si在后缀树中对应的叶节点P(Si)=N(Si)的父节点G(Si)=P(Si)的父节点，即N(Si)的祖父SL(p)=p的后缀连接所指向的节点W(p,q)=从p到q所经过的字符串root=后缀树的根节点后缀树的构造算法流程：定义SL(root)=root，首先插入S，此时后缀树中仅有两个节点。设已经插入了Si，现要插入Si+1。分情况讨论：1)P(Si)在插入Si之前已经存在。则P(Si)有后缀连接。令u=SL(P(Si))。从u开始沿着树往下查找，在合适的地方插入新的节点。2)P(Si)是在插入Si的过程中产生的。此时G(Si)必定存在并有后缀连接。令u=SL(G(Si)，w=W(G(Si),P(Si))。从u开始，对w进行快速定位找到节点v（注意，v可能需要通过分割边来得到）。令SL(P(Si))指向v。从v开始沿着树往下查找，在合适的地方插入新的节点。不断重复以上过程，即可完成整棵后缀树的构造。