导言
最近软件安全课上，讲病毒特征码的提取时，老师讲了一下GST算法。这里就做个小总结。
简介
基本信息 广义后缀树的英文为Generalized Suffix Tree，简称GST。
算法目的 GST算法的提出是为了解决最大公共子串问题，也就是在多个字符串中，找到他们共有的子串。
顺便说一句
这个问题听起来和最大公共子序列问题（LCS）有些相似，但是二者有两个不同点：
①一个是公共子串，一个是公共子序列，后者可以是不连续的；
②GST算法可以对多个字符串求公共子串，而我们一般指的LCS算法只能对两个字符串求公共子序列。
下面继续介绍GST。
原理
后缀树，顾名思义，是一个字符串的所有后缀构成的一棵树。那么我们为什么要把一个字符串的所有后缀，提取出来呢？
对于"p in S?"这个问题，我们假设S=rpq，这时我们看到pq是S的后缀，p为S的后缀pq的前缀。
也就是说，如果p在S中出现，那么我们一定能找到S的一个后缀，使得p是这个后缀的前缀。因此，为了判断"p in S?"这个问题，我们将S所有的后缀提取出来，与p进行比对。为了加快比对的效率，我们把所有的后缀建成一棵树。
举个例子
比如字符串aboreabo，它的后缀按长度依次为
- o
- bo
- abo
- eabo
- reabo
- oreabo
- boreabo
- aboreabo
将它们按字典序排序
- abo
- aboreabo
- bo
- boreabo
- eabo
- o
- oreabo
- reabo
则这棵树如下
好吧，这棵树怪怪的。换了例子吧。对于字符串abcadabf，它的后缀树如下
额。。。这棵树也怪怪的，看起来很像苏联的工业和农业。。。
不管了继续说吧。
接着说原理
上面我们，那么如果p in S1，p in S2，那么p是S1和S2的子串。因此，对于多个字符串S1,S2,……,Sn，建立一颗包含它们全部后缀的后缀树，那么重合的节点就是他们的公共子串了。
再举个例子
我们举个例子吧。对于{abcde,cdef,ccde}，首先对abcde建立后缀树，如下
然后把cdef的所有后缀加进去，得到下面的树
最后把ccde的所有后缀加进去，
这是，我们可以看到，cde就是{abcde,cdef,ccde}的最长公共子串了。
作业真多，写到这里。