后缀自动机的一点点理解 by yyb

发布于 2018-02-13  14 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:后缀自动机的一点点理解 by yyb

后缀自动机的一点点理解

潜在可能格式挂了,yyb博客地址

前言

最近心血来潮,想学学SAM,于是花了一晚上+一上午
勉强打了出来(但是还是不理解)
虽说张口就讲我做不到
但是一些其他的东西还是有所感触的
索性,乱口胡点东西,谢谢关于SAM的一些简单的理解

资料

丽洁姐WC PPT
hihocoder上的后缀自动机

一些概念

这些概念都不读懂,接下来真的是步履维艰

本来我们要的是一个能够处理所有后缀的数据结构
但是我们发现,如果对于每一个后缀都要插入进Trie树
空间复杂度完全背不动(O(n^2)级别)
于是,后缀自动机出现了
后缀自动机相比于Trie树
在空间上有了很大的改善,他的空间复杂度是O(n)级别的
(详见丽洁姐的PPT)

杂七杂八的没有什么太多写的必要,网上一找一大堆
写写一些概念

right/endpos

hihocoder上写的是endpos集合
其他的大部分地方写的是right集合
这就是最基础的概念了
叫做endpos的话应该很好理解,所以我就写endpos
endpos就是一个子串结束位置组成的集合
对于所有结束位置相同的子串
也就是endpos相同的两个子串
他们一个一定是另一个的后缀

至于证明,简单的想一下,如果一个子串出现在了若干个位置
那么他的后缀也一定出现在了这些位置(只可能出现在更多未知,不可能更少)

同时,得到了一个推论:
两个字符串如果有一个是另一个的后缀,
那么,较长串的endpos一定是较短串的endpos的子集
(就是上面写的,只可能多,不可能少)
同样的,如果没有后缀的关系,那么它们的endpos的交集一定是空集

而后缀自动机的每个节点就是依照endpos来划分
对于endpos相同的子串,我们可以划分在一起
我们不难得出一点,对于一堆endpos相同的子串
他们一定互为后缀,并且他们长度连续

首先证明互为后缀,那就是上面的那个推论,
如果不是互为后缀的话,endpos就不可能相等
而长度连续?
既然互为后缀,那就一定有一个最长的串,不妨记为longest
那么,所有的其他串一定是他的后缀
随着后缀长度的减小,
那么从某一个后缀开始,就可能出现在了更多的位置
那么,这个后缀以及比它更短的后缀的endpos一定会变大
此时他们就会分到别的节点去了
因此,具有相同endpos的子串一定长度连续,互为后缀
另外一个简单的结论,确定了endpos和长度len就能确定唯一的子串

trans

trans不难理解是转移的意思
trans(s,c)表示当前在s状态,接受一个字符c之后所到达的状态
一个状态s表示若干endpos相同的连续子串
那么,此时相当于在后面加上了一个字符c
那么,我们对于任意一个串直接加上一个字符c之后
组成的串的endpos还是相同的
所以trans(s,c)就会指向这个状态
换句话说,随便在当前状态s中找一个串(比如longest
然后在后面接上一个c
那么,就指向包含这个新字符串的状态

Parent/Suffix Links

本质上也是一个东西,不同的地方写的不一样而已
不妨设一个状态中包含的最短的串叫做shortest
那么,我们就知道shortest的任意一个非自己的后缀一定就会出现在了更多位置
他的最长的那个后缀,也就是减去了第一个字符后的串
就会出现在另外一个状态里面,并且是那个状态的longest
为什么?因为出现在了更多的位置,我们还是知道他是连续的子串
如果存在一个更长的串
那么,只可能是当前状态的shortest
但是shortest属于当前状态,而没有出现在更多的位置
因此,longest一定是当前状态的shortest减去最前面字符形成的串

那么,当前位置的parent就会指向那个状态

当然,还是有几个很有趣的性质
假设当状态是s
s.shortest.len=parent.longest.len+1
这个就是前面所说的东西,所以,对于每个状态,就没有必要记录shortest
因为你只要知道parent就可以算出来了

其次,sendposparent的子集
这个不难证明,因为parent包含了更多的位置

如果trans(s,c)\neq NULL
那么,trans(parent,c)\neq NULL
因为如果trans(s,c)存在这个状态
那么parent的串加上c之后,一定还是s+c后的后缀
所以也一定存在trans(parent,c)
所以,你可以认为parent是一个完全包含了s的状态
也正因为如此,parentendpos就是所有儿子endpos的并集

将所有的parent反过来,我们就得到了parent
如果要处理什么,就需要parent树的拓扑序
(因为parent相当于包含了所有的他的子树,都需要更新上去)
其实不需要拓扑排序
我们知道sendpos完全被parentendpos包含
s.longest一定长于parent.longest
所以,一个状态的longest越长,它一定要被更先访问
所以,按照longest的长度进行桶排序就可以解决拓扑序了

extend

对于一个SAM的构造
我们当然在线了(因为我只会这个)
我们依次加入字符c,来进行构造

假设原来的字符串是T
首先,一定会有一个新节点
因为新加入了一个字符后,一定出现了这个新的字符串T+c
此时endpos一定是新的位置
同时,原来的T的最后一个位置也可以通过+c变到这个新位置
设原来的最后一个位置的状态是last,新的状态是np
所以trans(last,c)=np
根据前面的东西,我们知道last的祖先们一定也会有这个trans
我们要怎么解决他呀

p=last
一直沿着parent往前跳,也就是不断令p=p.parent
所以p代表的,就是越来越短的T的后缀
因为要更新的是最后的位置,
只有当存在T的最后一个位置时才能更新

如果trans(p,c)=NULL,直接令trans(p,c)=np
很显然是可以直接在后面添加一个c到达np
如果跳完后发现没有parent了,直接把np.parent指向1
也就是空串所代表的状态

如果某个trans(p,c)不为NULL
那么,设q=trans(p,c)
如果有longest(p)+1=longest(q)
什么意思?
p的串后面添上一个c之后就是q状态
没有任何问题,直接在作为T的后缀的那一个子串上
直接添加一个c显然也可以到达q状态
又因为np所代表的endpos更小,
所以np.parent=q

在否则的话
也就是longest(q)>longest(p)+1
具体的反例看丽洁姐PPT第35
如果直接插入的话(也就是np.parent=q
相当于给qendpos强行插入一个q
但是,我们发现,如果强行插入进去
这个T+c的后缀会出现在更多的位置,应该属于另外一个状态
然后就GG
此时,我们新建一个点nq
相当于把q拆成两部分:
一部分是T+c的那个后缀,一个是longest(p)+c
也就是longest(nq)=longest(p)+1
显然T+c的后缀是包含了状态较少的,
拆分出来的一部分q是长度较长的
所以q.parent=np.parent=nq
同时,继续沿着pparent往上走
把所有的q都替换成nq

看起来很有道理,但是我也是似懂非懂的感觉

End

这就是我自己的一些没有什么用的总结了
我觉得题目才能真正反映SAM的作用
到时候再补点题目上去

补一份后缀自动机extend的代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:后缀自动机的一点点理解 by yyb


我是蒟蒻yyb 我太弱了 我还要多切大火题 我才能变得像zsy那么优秀