后缀数据结构.ppt

Company Logo LOGO 石家庄二中 秦岳 后缀数据结构Suffix Data Struct 后缀树(Suffix Tree) 后缀树是一种功能强大的字符串处理数据结构，能快速解决很多关于字符串的问题。 朴素的将字符串S的所有合法后缀插入Trie树中所形成的树结构成为后缀Trie,结点个数为O(N^2)。 其中后缀Trie的根以及所有后缀的结束结点均为关键点。 发现如果一个非关键结点只有一个儿子时，我们不用保存此结点，只需将父亲边与之合并成一条复合边即可保留原树所有信息。由于后缀Trie实际只由O(N)个后缀字符串构成，所以化简之后形成的树只由O(N)个节点。 化简后的Trie树称为后缀树。 图例(Simple) 后缀树的附加记录信息 ①记录后缀→结点的双向映射 ②结点的最近公共祖先极为其最长公共前缀(Trie) ③结点DFS序靠前的字符串字典序小(Trie) ④记录结点所代表最长字符串的长度为len ⑤原串是否存在某子串→Trie上能否走下去 ⑥每颗子树内有多少个后缀→有多少个子串为子树根(Tree) 后缀树的朴素构造与信息存储 对于一个后缀树的结点建立与Trie基本相同，唯一的不同是树边的标示为原字符串中的某个子串S[l,r]。 结点结构： int tot,M=26; struct Node{ int son[M],l[M],r[M]; }; 朴素构造法： 深度优先：依次插入每个后缀，只有当出现分叉或结尾时新建结点。 宽度优先：将所有后缀按位同时插入后缀树，当遇到结尾或分支时建立结点。 时间复杂度:O(N^2) 空间复杂度：O(N) 易知插入一个字符串最多新建两个结点。 广义后缀树 对于字符串集合T={t1,t2…tn}的广义后缀树，是一个压缩字典树(trie)其中包含了T中每一个字符串的所有的后缀。 简而言之，就是一个将所有字符串的所有后缀插入Trie树并进行路径压缩之后形成的树结构。 广义后缀树的附加记录信息 ①包含后缀树的所有信息 ②通过记录每个后缀结点的属于哪个字符串可以对不同串分类统计 ③广义后缀树中存在的字符串至少一个字符串的子串。 ④字符串出现了几次→广义后缀树中对应结点所在子树后缀结点数 后缀自动机(Suffix Automaton) 给定字符串S，S的后缀自动机(SAM)能识别字符串A，当且仅当A是S的后缀。 广义多串后缀自动机： 给定字符串集合{S}，{S}的后缀自动机能识别字符串A，当且仅当A是{S}中至少一个元素的后缀。 备注：可以将后缀Trie的结构当做SAM，但是状态量过大。 后缀树结点的previous指针 为了方便理解后缀自动机的构造原理与线性时间后缀树的构造原理，我们对后缀树上的每一个结点定义其pre指针，设结点x代表字符串cA(c为字符，A为字符串)，则pre[x]指向后缀树中的A，称x的pre标识为c，pre[x]为x的前驱，x为pre[x]的c后继。 定义转移函数：tranc(pre[x],c)=x 后缀Trie的previous指针 定义同上，观察图例： 我们将红点定义为后缀结束点，绿点定义为分支中继点，白点定义为被后缀树压缩掉的无用假点。 Previous指针的性质 ①关键点的pre同为关键点 ②pre指向同一结点时，其标识必定互不相同 ③关键点及其相连的一段白点祖先tranc(p,x)存在性相同 ④若点p存在tranc(p,c)，则其祖先同样存在tranc(p’,c) 证明①： 1.一个后缀结点的pre显然是一个后缀结点，故为关键点。 2.一个中继结点的pre一定是一个中继节点，故为关键点。证：设中继节点表示xA,由于他为中继所以必然有两个不同的字符a、b构成的后缀形成xAb和xAc两条链，故必然存在Aa和Ab两条链，故A为中继节点。 证明②：将结点定义为cA,对于pre均指向A的结点，若标识相同则c部分相同，则cA为同一结点。 证明③：这一部分点为根的子树中红点相同，故这些后缀前一个字符是否有c的存在性也相同。 证明④：显然若原串包含cAx,则必然包含cX。 后缀树→逆序后缀自动机 将字符串S的后缀Trie中所有白点的pre压缩至其最近关键点儿子上，并删除白点，并去除重边形成的压缩pre版本的后缀树。 我们根据压缩后缀树及其pre/tranc(p,x)构造逆序S字符串的后缀自动机： 压缩后缀树的结点为后缀自动机的所有状态；tranc(p,x)为后缀自动机状态p的x转移边；树链S为后缀自动机的全部接受状态。 由于pre结构复杂，所以存储时我们只pre的反向边tranc记录在点上 压缩pre后缀树的性质 ①指向同一结点的若干pre ，其标识必定互不相同(证明同上) ②所有状态互不相交，且并集为S的全部子串(后缀树性质显然) ③通过逆pre边转移至同